LeetCode 2956. 找到两个数组中的公共元素

在本篇文章中，我们将探讨如何求解 LeetCode 上的 2956. 找到两个数组中的公共元素问题。这个问题要求我们找到两个数组中公共元素的出现次数，并分别计算这些公共元素在各自数组中的出现次

问题描述 

算法分析

为了解决这个问题，我们可以采用以下步骤：

1. 排序：首先对两个数组进行排序。排序后，相同的元素会相邻，这有助于我们快速找到公共元素。

2. 统计出现次数：使用两个数组（或哈希表）来统计 nums1 和 nums2 中每个元素的出现次数。

3. 计算公共元素的出现次数：遍历两个数组，找到公共元素，并计算这些公共元素在各自数组中的出现次数。

代码实现

以下是使用 C++ 实现的代码：

#include <vector>
#include <algorithm>
#include <unordered_map>

class Solution {
public:
    std::vector<int> findIntersectionValues(std::vector<int>& nums1, std::vector<int>& nums2) {
        // 对两个数组进行排序
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());

        // 使用哈希表统计nums1和nums2中元素的出现次数
        std::unordered_map<int, int> countNums1;
        std::unordered_map<int, int> countNums2;

        for (int num : nums1) {
            countNums1[num]++;
        }
        for (int num : nums2) {
            countNums2[num]++;
        }

        int ans1 = 0, ans2 = 0;
        // 遍历nums1，找到公共元素，并计算在nums2中的出现次数
        for (const auto& pair : countNums1) {
            if (countNums2.find(pair.first) != countNums2.end()) {
                ans1 += pair.second;
            }
        }
        // 遍历nums2，找到公共元素，并计算在nums1中的出现次数
        for (const auto& pair : countNums2) {
            if (countNums1.find(pair.first) != countNums1.end()) {
                ans2 += pair.second;
            }
        }

        return {ans1, ans2};
    }
};

复杂度分析

• 时间复杂度：O(n log n + m log m)，其中 n 和 m 分别是 nums1 和 nums2 的长度。主要时间消耗在排序上。

• 空间复杂度：O(n + m)，用于存储两个数组中元素的出现次数。

结论

通过排序和统计出现次数的方法，我们可以有效地找到两个数组中的公共元素，并计算这些公共元素在各自数组中的出现次数。这种方法简单且高效，适用于处理大规模数据。