LeetCode Intersection of Two Arrays II Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2]. Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

---

求两个数组的交集，这里的交集又不同之前LeetCode Intersection of Two Arrays的交集了，这里的交集不再满足集合的互异性，两个数组中有多个同一个数，有几个共有，交集里就有几个，看例子就知道了。 这其实简化了问题，我们对其中一个数组hash，建立数字和频率的hash表，然后遍历另一个数组，hash表中有，则加入交集，同时hash中的频率减1，也不需要对结果去重了。完整代码如下： [cpp] class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> hash; vector<int> ans; for (int i = 0; i < nums1.size(); ++i) { ++hash[nums1[i]]; } for (int i = 0; i < nums2.size(); ++i) { if (hash[nums2[i]]>0) { ans.push_back(nums2[i]); –hash[nums2[i]]; } } return ans; } }; [/cpp] 本代码提交AC，用时6MS。 回答一下Follow up的三个问题： 如果数组已排序，则可以用归并排序的思路求交集，两个指针i,j分别指向两个数组，然后判断nums[i]==nums[j]，如果相等，则加入交集，i,j都往后移；否则根据大小关系选择后移i或j。 不过我觉得代码中的Hash思路已经够快了，时间复杂度应该都是O(n1+n2)，只不过Hash毕竟需要计算Hash值，Hash占用的隐性空间也比较大，所以归并的思路可能会快一些。 如果nums1.size<nums2.size()，则归并的思路会快一些，因为归并的话，其实复杂度是O(min(n1,n2))，当一个数组的指针走到头之后，算法就结束了，而Hash的话，就必须走完两个数组。 如果nums2不能一次load进内存，则分批load内存查Hash。]]>