Intersection of Two Arrays II

350. 两个数组的交集II

分析

由于交集的每个元素的出现次数需要和两个数组中的最小出现次数一致，因此需要一个数据结构来存储 nums1 中每个元素的个数
由于 std::unordered_multiset 允许存储重复元素，所以可以用它来存储 nums1 的所有元素
遍历 nums2，检查当前元素是否在 unordered_multiset 中，如果存在，则加入结果数组，并从 unordered_multiset 中删除该元素，以确保每个元素只被匹配一次

时间复杂度

时间复杂度 O(n + m)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
    {
        std::vector<int> res;
        std::unordered_multiset<int> hash;

        // 1. 统计 nums1 的元素频次
        for (int x : nums1)
            hash.insert(x);

        // 2. 遍历 nums2，检查是否在 hash 中
        for (int x : nums2)
            if (hash.count(x))  // 如果 x 在 hash 中
            {
                res.push_back(x);  // 加入结果数组
                hash.erase(hash.find(x));  // 删除 hash 中的一个 x（防止重复计数）
            }

        return res;
    }
};