ACM 选手图解 LeetCode 之两个数组的交集

简介: ACM 选手图解 LeetCode 之两个数组的交集

大家好呀,我是帅蛋。


今天来解决两个数组的交集,继续通过实战题目的巩固,玩转哈希表!

640.png


   LeetCode 349:两个数组的交集


题意


给定两个数组,计算它们的交集。


示例


输入:nums1 = [4, 9, 5],nums2 = [9, 4, 9, 8, 4]

输出:[9, 4]

提示


  • 输出结果中的每个元素一定是唯一的。
  • 我们可以不考虑输出结果的顺序。


题目解析


水题,难度简单。


就一句话:求两个数组的交集,直白点儿就是nums2 的元素是否在 nums1 中】。


需要注意一下“提示”里讲的:输出结果中的每个元素一定是唯一的,翻译一下就是去重输出。


这道题为啥能用哈希做呢?


我在之前LeetCode202 快乐数】中讲过:在一堆数中查找一个数,当然是扔出哈希,毕竟是查找中的秒男,时间复杂度为 O(1)。


这道题和快乐数有些相似的地方:这道题同样也没限制数值的大小,所以就不能用数组来做哈希表。

640.jpg


碰到这种对目前来说是未知数值大小的情况,我们可以使用集合 set 来解决。


用 set 爽归爽,在这里我建议还是不要直接用库函数。


大家用的编程语言可能不尽相同,最好是用编程语言自带的数据结构来模拟一下,毕竟对于初学者来说,还是得脚踏实地一步步的搞。

640.jpg


图解


以 nums1 = [4, 9, 5],nums2 = [9, 4, 9, 8, 4] 为例。


首先初始化一个哈希表和一个结果列表。

# 初始化哈希表
hash = {}
# 初始化结果列表,存放最后结果
res = []


第一步,遍历数组 nums1,将出现的数存进哈希表中。


nums1 数组中,第 1 个元素为 4,将其加入哈希表,对应数值置为 1。

640.png

# 哈希表 key 为 nums1 数组中的数,value 为值
for i in nums1:
    if not hash.get(i):
        hash[i] = 1

因为【输出结果中的每个元素一定是唯一的】,所以对于 key 所对应的 value 来说“数值是多少”就无所谓了,所以在本题中,不管某个元素在数组中出现多少次,我把 value 都置为 1。


遍历完数组 nums1,哈希表如下图所示:


640.png


第二步,遍历 nums2 数组,nums2 数组中的元素如果出现在哈希表中,则证明是和 nums1 数组相交的元素,则加入结果列表中。


nums2 数组中,第 1 个元素为 9,9 在哈希表中,则元素 9 加入结果列表,哈希表中该元素置为 0。

640.png

# 遍历 nums,如果 nums2 数组中的数出现在哈希表中,对应数放入结果列表,对应 value 值置-为0
for j in nums2:
    if hash.get(j):
        res.append(j)
        hash[j] = 0

同样遍历完 nums2,最后的结果变为下图所示:


640.png



res 就是最终的结果。


本题解遍历了 nums1 和 nums2 数组,所以时间复杂度为 O(n + m),n 和 m 分别为两个数组的长度。


额外建了一个哈希表,所以空间复杂度为 O(max(n, m))


代码实现


Python 代码实现

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 有一个数组为空,则交集为空
        if not nums1 or not nums2:
            return []
        # 初始化哈希表
        hash = {}
        # 初始化结果列表,存放最后结果
        res = []
        # 哈希表 key 为 nums1 数组中的数,value 为值
        for i in nums1:
            if not hash.get(i):
                hash[i] = 1
        # 遍历 nums,如果 nums2 数组中的数出现在哈希表中,对应数放入结果列表,对应 value 值置-为0
        for j in nums2:
            if hash.get(j):
                res.append(j)
                hash[j] = 0
        return res


Java 代码实现

import java.util.HashSet;
import java.util.Set;
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历 nums1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历nums2,判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        int[] resArr = new int[resSet.size()];
        int index = 0;
        for (int i : resSet) {
            resArr[index++] = i;
        }
        return resArr;
    }
}


图解两个数组的交集到这就结束辣。


这是哈希实战的第 4 题,不知道大家有没有发现我的小心思:


第 1 题【LeetCode242 有效的字母异位词】和第 2 题【LeetCode383 赎金信】,第 3 题【LeetCode202 快乐数】和两个数组的交集是一类题。


相同类型的题刷多了,你就会发现,最后其实在你脑子里记住的不是实现这道题的代码,而是解这道题的思路。


等什么时候出现类似“这道题我见过,我知道用这样哪样的方法可以做出来”,小婊贝们就快出师了。


大家加油!也记得帮我点赞 + 在看呀。


我是帅蛋,我们下次见!

相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
1月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
19 4
|
1月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
18 0
Leetcode第三十三题(搜索旋转排序数组)
|
1月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
57 0
|
1月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
16 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
3月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组