349. 两个数组的交集

题目描述

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

示例 1：

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

示例 2：

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

说明：

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

思路

使用集合

c++中集合有基于红黑树的set还有哈希的unordered_set，使用集合可以去除重复。

将nums1放入哈希表s1中，遍历nums2，若元素在s1中，加入结果集合ans中，最后将其转化为vector。、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s1(nums1.begin(), nums1.end());
        unordered_set<int> ans;
        for(auto num:nums2) {
            if(s1.find(num) != s1.end()) {
                ans.insert(num);
            }
        }
        vector<int> res(ans.begin(), ans.end());
        return res;
    }
};

排序，双指针

排序之后利用双指针，注意加入时去重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> res;
        int i = 0, j = 0, n1 = nums1.size(), n2 = nums2.size();
        while(i < n1 && j < n2) {
            // 去重复
            if(nums1[i]==nums2[j] && (res.size()==0 || res.back() != nums1[i])) {
                res.push_back(nums1[i]);
                ++i,++j;
            } else if(nums1[i] > nums2[j]) {
                ++j;
            } else {
                ++i;
            }
        }
        return res;
    }
};