利用unordered_map特性求交集

unordered_map 是关联容器，含有带唯一键的键-值 pair 。搜索、插入和元素移除拥有平均常数时间复杂度。

元素在内部不以任何特定顺序排序，而是组织进桶中。元素放进哪个桶完全依赖于其键的哈希。这允许对单独元素的快速访问，因为一旦计算哈希，则它准确指代元素所放进的桶。

让我们看下原题：
给定两个数组，编写一个函数来计算它们的交集。

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

注意：

结果中的每个元素应该出现在两个数组中显示的次数。
结果可以是任何顺序。

优化：

如果给定的数组已经排序怎么办？ 你会如何优化你的算法？
如果nums1的尺寸与nums2的尺寸相比较小怎么办？ 哪种算法更好？
如果nums2的元素存储在磁盘上，并且内存有限，以致您无法一次将所有元素加载到内存中，该怎么办？

代码分析：

class Solution {
public:
    vector<int> intersect(vector<int>& a, vector<int>& b) {
        unordered_map<int, int> ctr;
        for (int i : a)
            ctr[i]++;
        vector<int> out;
        for (int i : b)
            if (ctr[i]-- > 0)
                out.push_back(i);
        return out;
    }
};