Given two arrays, write a function to compute their intersection.
Example:
Given nudms1 =[1, 2, 2, 1], nums2 =[2, 2], return[2].Note:
1.Each element in the result must be unique.
2.The result can be in any order.
题目大意，给出两个数组，要求求出两个数组的交集。并且交集结果中的元素是不重复的。
（1）首先将一个数组nums1存储在一个set容器中，随后遍历第二个数组nums2，查找其元素在set容器中是否存在相同的元素。若存在，则是交集的一部分并将相同元素insert入第二个set中(解决了元素唯一性的问题)。再将set转存到vector容器中。
解法一
|
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> iset1(nums1.begin(), nums1.end()), iset2; for (int i : nums2) { if (iset1.find(i) != iset1.end()) iset2.insert(i); } return vector<int>(iset2.begin(), iset2.end()); } }; |
（2）解法一使用了两个set容器，第一个set用来存储第一个数组nums1(消除了数组中的重复元素)；第二个set用来存储相同数字的元素(也消除了重复的元素)。下面这个解法只使用了一个set容器：首先如解法一讲nums1存储在set容器中，判断nums2中的元素是否有与在set中相同的元素，若有，则push_back到vector中，同时在set中删除该元素(保证了数据的唯一性)。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> iset(nums1.begin(), nums1.end()); vector<int> res; for (int i : nums2) { if (iset.count(i)) res.push_back(i); iset.erase(i); } return res; } }; |
（3）使用哈希表unordered_map。将数组nums1存储到哈希表中，为了实现类似set元素的唯一性，此处要加一个判断(如果该元素对应的值为0，则置为1)；然后遍历nums2，若nums2的元素在哈希表中(元素对应的值为1)，则push_back入vector中，并且递减其元素对应的值(保证了元素的唯一性)。
解法三
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_map<int,short> imap; vector<int> res; for (int &i : nums1) if (imap[i] == 0) ++imap[i]; for (int &i : nums2) if (imap[i]-- == 1) res.push_back(i); return res; } }; |
附：
（1）容器set的特性及用法，set中的元素是唯一的。
（2）哈希表unordered_map的特性及用法，因为unordered_map容器中的元素不具有唯一性，即同一个key可能出现多次。所以此题需要加一条判断语句，实现其类似set容器的特性。