349. Intersection of Two Arrays
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
- Each element in the result must be unique.
- The result can be in any order.
分析
使用一个hash table来记录nums1中的所有数字是否出现，然后在遍历nums2的所有数字，如果存在，则压入结果，并且把hash table对应值 设 false，保证不再重复压入结果。
空间复杂度：O(N)
时间复杂度：O(N)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,bool> m_map;
vector<int> result;
for(auto n:nums1){
m_map[n] = true;
}
for(auto n:nums2){
if(m_map.find(n) != m_map.end() && m_map[n] == true){
result.push_back(n);
m_map[n] = false;
}
}
return result;
}
}; |
或者使用set来做，用nums1初始化m_set，从而消除重复元素，
遍历nums2，并调用m_set的erase函数，成功，则push进result。erase返回删除的元素个数，因为set中元素都是unique的，成功返回1，失败返回0；通过set的特性，来消除重复元素的判断
|
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> m_set(nums1.begin(), nums1.end());
vector<int> result;
for(auto n: nums2){
if(m_set.erase(n))result.push_back(n);
}
return result;
}
}; |