题目描述

给定两个数组，请写一个函数计算它们的交集。

注意：

• 每个数在结果中出现的次数，需要和它在两个数组中出现的次数相同；
• 结果可以以任意顺序输出；

思考题：

1. 如果给定的数组已经排好序，你可以怎样优化你的算法？
2. 如果数组nums1的长度小于数组nums2的长度，哪种算法更好？
3. 如果数组nums2存储在硬盘上，然而内存是有限的，你不能将整个数组都读入内存，该怎么做？

样例

给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 
返回 [2, 2].

算法

(哈希表) $O(n + m)$

首先先将nums1存入哈希表中，注意这里要用unordered_multiset<int>，而不是unordered_set<int>，因为数组中含有重复元素。

然后遍历nums2，对于每个数 $x$，如果 $x$ 出现在哈希表中，则将 $x$ 输出，且从哈希表中删除一个 $x$。

时间复杂度分析：假设两个数组的长度分别是 $n, m$。将nums1存入哈希表的计算量是 $O(n)$，遍历nums2的计算量是 $O(m)$，所以总时间复杂度是 $O(n + m)$。

思考题：

1. 如果给定的数组已经排好序，你可以怎样优化你的算法？
   答：可以用双指针扫描。这样可以把空间复杂度降为 $O(1)$，但时间复杂度还是 $O(n)$；
2. 如果数组nums1的长度小于数组nums2的长度，哪种算法更好？、
   答：可以把nums1存入哈希表，然后遍历nums2。这样可以使用更少的内存，但时空复杂度仍是 $O(n)$；
3. 如果数组nums2存储在硬盘上，然而内存是有限的，你不能将整个数组都读入内存，该怎么做？
   答：如果nums1可以存入内存，则可以将nums1存入哈希表，然后分块将nums2读入内存，进行查找；如果两个数组都不能存入内存，可以先将两个数组分别排序，比如可以用外排序，然后用类似于双指针扫描的方法，将两个数组分块读入内存，进行查找。

C++ 代码

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_multiset<int> S;
        vector<int> res;
        for (int x : nums1) S.insert(x);
        for (int x : nums2)
            if (S.count(x))
            {
                res.push_back(x);
                S.erase(S.find(x));
            }
        return res;
    }
};