题目
分析
数组元素值可以很大,所以不适合直接开数组进行哈希,这里要学习另一种哈希方式:集合
集合有三种,区别见下面代码随想录的Carl大佬的表格,总结的很清晰。
由于题目中明确了不考虑元素的是否有序,所以我们可以使用unordered_set,这样查删效率会高些。
代码
1 class Solution {
2 public:
3
4 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
5 unordered_set<int>n1(nums1.begin(),nums1.end());
6 vector<int>res;
7 // unordered_set<int>res;
8 // for(int i = 0;i < nums2.size();i++){
9 // if(n1.find(nums2[i]) != n1.end())
10 // res.insert(nums2[i]);
11 // }
12 // return vector<int>(res.begin(),res.end());
13
14 for(auto& num : nums2){
15 if(n1.find(num) != n1.end()){
16 res.push_back(num);
17 n1.erase(num);
18 }
19 }
20 return res;
21 }
22 };
这里先将nums1转换为unordered_set,去重,然后再遍历nums2找到nums1公共元素加入res
说明:
1. 14行为C++11特性,nums2的每个元素赋值给num。至于为什么加取地址符,是因为无论时
整形还是迭代器类型,使用引用类型可以避免多余的拷贝步骤
2. 15行,find如果没有找到该值,则返回一个容器尾部的迭代器