两个数组的交集

描述

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

unordered_set

初始化

unordered_set<int> set1; //创建空set
unordered_set<int> set2(set1);    //拷贝构造
unordered_set<int> set3(set1.begin(), set1.end());    //迭代器构造
unordered_set<int> set4(arr,arr+5);    //数组构造
unordered_set<int> set5(move(set2));    //移动构造
unordered_set<int> set6 {1,2,10,10};//使用initializer_list初始化

常用操作

set1.find(2);    //查找2，找到返回迭代器，失败返回end()
set1.count(2);    //返回指2出现的次数，0或1
set1.emplace(3);    //使用转换移动构造函数，返回pair<unordered_set<int>::iterator, bool>
set1.insert(3);    //插入元素，返回pair<unordered_set<int>::iterator, bool>
set1.insert({1,2,3});    //使用initializer_list插入元素
set1.insert(set1.end(), 4);//指定插入位置，如果位置正确会减少插入时间，返回指向插入元素的迭代器
set1.insert(set2.begin(), set2.end());//使用范围迭代器插入
set1.erase(1);	    //删除操作，成功返回1，失败返回0
set1.erase(set1.find(1));	    //删除操作，成功返回下一个pair的迭代器
set1.erase(set1.begin(), set1.end());    //删除set1的所有元素，返回指向end的迭代器
set1.empty();        //是否为空
set1.size();        //大小
set1.bucket_count();    //返回容器中的桶数
set1.bucket_size(1);    //返回1号桶中的元素数
set1.bucket(1);    //1在哪一个桶
set1.load_factor();    //负载因子，返回每个桶元素的平均数，即size/float(bucket_count);
set1.max_load_factor();//返回最大负载因子
set1.max_load_factor(2);//设置最大负载因子为2，rehash(0)表示强制rehash
set1.rehash(20);//设置桶的数量为20，并且重新rehash
set1.reserve(20);//将容器中的桶数设置为最适合元素个数，如果20大于当前的bucket_count乘max_load_factor，则增加容器的bucket_count并强制重新哈希。如果20小于该值，则该功能可能无效。
unordered_set<int>::iterator it = set1.begin();	    //返回指向set1首元素的迭代器
unordered_set<int>::const_iterator c_it = set1.cbegin();	    //返回指向set1首元素的常量迭代器
unordered_set<int>::local_iterator it = set1.begin(1);//返回1号桶中的首元素迭代器
unordered_set<int>::const_local_iterator c_it = set1.cbegin(1);//返回1号桶中的首元素的常量迭代器
pair<unordered_set<int>::iterator, unordered_set<int>::iterator> it = set1.equal_range(1);//返回一个pair，pair里面第一个变量是lower_bound返回的迭代器，第二个迭代器是upper_bound返回的迭代器
set1.clear();        //清空

使用数组来做哈希的题目，是因为题目都限制了数值的大小。

而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：

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

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

思路如图所示：

代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;//存放结果，可以去重
        unordered_set<int> nums(nums1.begin(), nums1.end()); //范围迭代器构造
        for(int num: nums2){
            // 发现nums2的元素在nums_set里有出现过
            if(nums.find(num) != nums.end())
                result.insert(num);
        }
        return vector<int>(result.begin(), result.end());
    }
};

本题后面 力扣改了 题目描述 和 后台测试数据，增添了 数值范围：

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

所以就可以 使用数组来做哈希表了， 因为数组都是 1000以内的。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;//存放结果，可以去重
        int hash[1001] = {0};//初始化为0
        for(int num: nums1){
            hash[num] = 1;
        }
        for(int num: nums2){
            if(hash[num] == 1)
                result.insert(num);
        }
        return vector<int>(result.begin(), result.end());
    }
};