leetcode#349 两个数组的交集

发表于 2019-12-04  61 次阅读


文章目录

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<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        // 去重
        set<int> nums1_set(nums1.begin(), nums1.end());
        set<int> nums2_set(nums2.begin(), nums2.end());

        vector<int> result_vec;
        set<int>::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;
    }
};
本站文章基于国际协议BY-NA-SA 4.0协议共享;
如未特殊说明,本站文章皆为原创文章,请规范转载。

0

这里是柠檬酱,小水管服务器不要打我QAQ