LeetCode 349:两个数组的交集

简介: LeetCode 349:两个数组的交集

LeetCode 349:两个数组的交集

题意

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

示例

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

输出:[9, 4]

提示

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

题目解析

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

第一种解法

这道题字符串 num1 和 num2 仅包含1000以内,数字就固定的 1000个。

(不要我问我为什么1000以内,因为你has设到100以内报错~)

这种定长的范围且和字符次数相关,用哈希妥妥的没问题。

第一种解法  使用的哈希函数 f(key) = key - 0 。 (这道题思路沿用了242有效字母的异位词~) 哈希函数找好,下面的就很简单:

  1. 遍历字符串 num1,哈希表hash1对应的字符值加。
  2. 遍历字符串 num2,哈希表hash2对应的字符值加。
  3. 判断哈希表hash1不为0,并且hash2也不为0,则把重复的数字输送到result序列

代码实现

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        hash1=[0]*1000
        for i in range(len(nums1)):
            hash1[nums1[i]-0] +=1
        hash2=[0]*1000
        for i in range(len(nums2)):
            hash2[nums2[i]-0] +=1
        result=[]
        for i in range(1000):
            if hash1[i] != 0:
                if hash2[i] != 0:
                    result.append(i)
        return result
复制代码

网络异常,图片无法展示
|

第二种解法

这道题同样也没限制数值的大小,所以就不能用数组来做哈希表。

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

代码实现

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



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