leetcode#349 两个数组的交集

https://leetcode-cn.com/problems/intersection-of-two-arrays

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

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

说明:

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

思考

幼稚的方法是根据第一个数组 nums1 迭代并检查每个值是否存在在 nums2 内，如果存在将值添加到输出。这样的方法会导致 O(n×m) 的时间复杂性，主要是因为忌惮重复而不得不遍历完整整个数组。在这个过程完成以后，还要给数组本身去重。

我们可以考虑，先把输入的两个数组转换为set来去重，然后在内外for循环中遍历两个数组，如果发现出现相同元素就终止内循环并且push_back一个相同值。这样，不用遍历完整整个nums2数组，就直接可以输出本次遍历的结果。

当遍历完nums1以后，就得到了所有不重复的元素。

代码

class Solution
{
public:
    vector intersection(vector &nums1, vector &nums2)
    {
        // 去重
        set nums1_set(nums1.begin(), nums1.end());
        set nums2_set(nums2.begin(), nums2.end());

        vector result_vec;
        set::iterator nums1_it, nums2_it;
        for (nums1_it = nums1_set.begin(); nums1_it != nums1_set.end(); nums1_it++)
        {
            for (nums2_it = nums2_set.begin(); nums2_it != nums2_set.end(); nums2_it++)
            {
                if(*nums1_it == *nums2_it)
                {
                    result_vec.push_back(*nums2_it);
                    break;
                }
            }
        }
        return result_vec;
    }
};

python极简版

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        l1, l2 = set(nums1), set(nums2)
        res = []
        for i in l1:
            if i in l2:
                res.append(i)
        return res