349. 两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

示例 1：

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

示例 2：

1
2
3
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

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

思路

这道题目，主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。

第二种解法使用c语言实现，见下文。

使用数组来做哈希的题目，是因为题目都限制了数值的大小。如果没有限制数值的大小，就无法使用数组来做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。此时就要使用另一种结构体set。

关于set，C++ 给提供了如下三种可用的数据结构：

  • std::set
  • std::multiset
  • std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

在C++11，使用for循环遍历数组中的元素时可以这样：

for（int num ： nums）//其中，nums是数组名字。

unordered_set容器和vector容器一样，可以使用insert（）插入元素，begin（），end（）迭代器跳转到容器开头或者结尾，还可以用find（）查找容器中存储的值。

c++代码如下：

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> ans; //给结果去重用
        unordered_set<int> num_set(nums1.begin(),nums1.end());//初始化
        for(int num :nums2){
            if(num_set.find(num) != num_set.end()){
                ans.insert(num);
            }
        }
        return vector<int>(ans.begin(),ans.end());

    }
};

因为c语言没有unordered_set容器可供使用，且题目所给的数据有一个范围，虽然范围较大，用数组做的话浪费内存。

思路是，先构建一个hash数组，对hash数组中的num1[i]的位置写值，然后再 遍历num2数组，查找对应位置的hash数组有没有存值，有的话则说明元素重复。

c语言代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int min = nums1Size > nums2Size ? nums2Size:nums1Size;
   // int max = nums1Size > nums2Size ? nums1Size:nums2Size;
    int max =1005;
    int hash[max]; 
    int* ans = (int*)malloc(sizeof(int)*min);
    memset(hash,-1,sizeof(hash));
    int i;
    int j =0;
    for(i=0;i<nums1Size;i++){
        if( hash[nums1[i]] == -1){
            hash[nums1[i]] = nums1[i];
            }
    } 
    for(i=0;i<nums2Size;i++){
        if(hash[nums2[i]] == nums2[i]){
            ans[j] = nums2[i];
            hash[nums2[i]] = -1;
            j++;
        }
    }
    *returnSize = j;
    return ans; 
}