LeetCode 350、两个数组的交集II

你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 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.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

二、题目解析

三、参考代码

Java 代码

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> count1 = new HashMap<>();
        Map<Integer, Integer> count2 = new HashMap<>();
        List<Integer> result = new ArrayList<>();

        // Count occurrences in the first array
        for (int num : nums1) {
            count1.put(num, count1.getOrDefault(num, 0) + 1);
        }

        // Count occurrences in the second array
        for (int num : nums2) {
            count2.put(num, count2.getOrDefault(num, 0) + 1);
        }

        // Find the intersection of elements and add to the result list
        for (int key : count1.keySet()) {
            if (count2.containsKey(key)) {
                int commonCount = Math.min(count1.get(key), count2.get(key));
                for (int i = 0; i < commonCount; i++) {
                    result.add(key);
                }
            }
        }

        // Convert the list to an array
        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }

        return resultArray;
    }
}

C++ 代码

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> count1;
        unordered_map<int, int> count2;
        vector<int> result;

        // Count occurrences in the first vector
        for (int num : nums1) {
            count1[num]++;
        }

        // Count occurrences in the second vector
        for (int num : nums2) {
            count2[num]++;
        }

        // Find the intersection of elements and add to the result vector
        for (auto& entry : count1) {
            if (count2.find(entry.first) != count2.end()) {
                int commonCount = std::min(entry.second, count2[entry.first]);
                result.insert(result.end(), commonCount, entry.first);
            }
        }

        return result;
    }
};

Python 代码

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 用两个哈希表cnt1和cnt2计算两个数组中各个元素出现的评论
        cnt1 = Counter(nums1)
        cnt2 = Counter(nums2)
        ans = list()
        # 遍历其中一个哈希表中的键k，比如遍历cnt1，表示遍历nums1中所有出现过的元素
        for k in cnt1:
            # cnt1[k]和cnt2[k]分别表示元素k在nums1和nums2中出现的频率
            # 取min(cnt1[k], cnt2[k])表示取其中的较小值作为共同重复出现的次数
            # 再乘上[k]是列表的乘法，用于列表的构建
            # 譬如假设 min(cnt1[k], cnt2[k]) = 3
            # [k] * min(cnt1[k], cnt2[k])就得到[k, k, k]，构建了元素k重复3次的列表
            # 再将构建得到的列表延长到ans中
            ans += [k] * min(cnt1[k], cnt2[k])
        return ans

C代码

#include <stdlib.h>
#include <string.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    // 定义两个频率数组，用于存储数字出现的频率
    int count1[1001] = {0};
    int count2[1001] = {0};

    // 统计 nums1 中每个数字的频率
    for (int i = 0; i < nums1Size; i++) {
        count1[nums1[i]]++;
    }

    // 统计 nums2 中每个数字的频率
    for (int i = 0; i < nums2Size; i++) {
        count2[nums2[i]]++;
    }

    // 分配内存用于存储交集结果，最大可能为 nums1Size 或 nums2Size 的长度
    int* result = (int*)malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size));
    int resultIndex = 0;

    // 遍历所有可能的数字，找出它们在两个数组中的公共频率
    for (int i = 0; i < 1001; i++) {
        int commonCount = count1[i] < count2[i] ? count1[i] : count2[i];
        for (int j = 0; j < commonCount; j++) {
            result[resultIndex++] = i;
        }
    }

    // 设置返回数组的大小
    *returnSize = resultIndex;

    return result;
}

Node JavaScript代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    // 定义两个哈希表，用于存储数字出现的频率
    const count1 = {};
    const count2 = {};
    const result = [];

    // 统计 nums1 中每个数字的频率
    for (const num of nums1) {
        count1[num] = (count1[num] || 0) + 1;
    }

    // 统计 nums2 中每个数字的频率
    for (const num of nums2) {
        count2[num] = (count2[num] || 0) + 1;
    }

    // 遍历 count1 中的每个键，计算公共频率并添加到结果数组
    for (const num in count1) {
        if (count2[num]) {
            const commonCount = Math.min(count1[num], count2[num]);
            for (let i = 0; i < commonCount; i++) {
                result.push(Number(num));
            }
        }
    }

    return result;
};

Go代码

func intersect(nums1 []int, nums2 []int) []int {
    // 定义两个频率映射表
    count1 := make(map[int]int)
    count2 := make(map[int]int)
    result := []int{}

    // 统计 nums1 中每个数字的频率
    for _, num := range nums1 {
        count1[num]++
    }

    // 统计 nums2 中每个数字的频率
    for _, num := range nums2 {
        count2[num]++
    }

    // 遍历 count1，计算公共频率并添加到结果数组
    for num, freq1 := range count1 {
        if freq2, exists := count2[num]; exists {
            commonCount := min(freq1, freq2)
            for i := 0; i < commonCount; i++ {
                result = append(result, num)
            }
        }
    }

    return result
}

// 辅助函数：计算两个数的最小值
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

时空复杂度

时间复杂度：O(n+m)。构建哈希表、遍历哈希表所的时间复杂度。

空间复杂度：O(n+m)。哈希表所占用额外空间。