【C++刷题】力扣-#350-两个数组的交集II

题目描述

给定两个数组 nums1 和 nums2，返回两个数组的交集，且每个元素出现的次数是两个数组中该元素出现次数的最小值。换句话说，如果元素 x
在 nums1 中出现了 a 次，在 nums2 中出现了 b 次，那么在返回的交集中，x 出现的次数应该是 min(a, b)。

示例

示例 1:

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

题解

这个问题可以通过使用哈希表来解决。

1. 初始化哈希表：创建一个哈希表来存储 nums1 中的元素及其出现次数。
2. 构建哈希表：遍历 nums1，更新哈希表中的计数。
3. 查找交集：遍历 nums2，对于 nums2 中的每个元素，检查它是否存在于哈希表中，并且哈希表中的计数是否大于 0。
   ○ 如果存在，并且计数大于 0，则将其添加到结果列表中，并减少哈希表中的计数。
4. 返回结果：返回结果列表。

代码实现

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> countMap;
    vector<int> intersection;
    for (int num : nums1) {
        countMap[num]++;
    }
    for (int num : nums2) {
        if (countMap.find(num) != countMap.end() && countMap[num] > 0) {
            intersection.push_back(num);
            countMap[num]--;
        }
    }
    return intersection;
}

复杂度分析

● 时间复杂度：O(n + m)，其中 n 是 nums1 的长度，m 是 nums2 的长度。我们需要遍历两个数组，并且对于 nums2 中的每个元素，我们进行常数时间的哈希表查找。
● 空间复杂度：O(n)，我们需要存储 nums1 中的所有元素到哈希表中。
这个算法的优势在于它的时间效率较高，只需要一次遍历即可找到两个数组的交集，且直接利用了哈希表的快速查找特性。