两个数组的交集 II

题目描述
给定两个整数数组 nums1 和 nums2，返回它们的交集（交集指同时出现在两个数组中的元素），要求结果中每个元素出现的次数与它在两个数组中出现的最小次数一致，输出顺序任意。

示例

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

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

解题思路

方法一：哈希表计数（适用于任意规模数组）

核心思想：使用哈希表记录较小数组中每个数字的出现次数，遍历另一个数组时匹配并减少计数。

步骤：

1. 选择较小的数组进行哈希计数（减少空间占用）。
2. 遍历另一个数组，若当前数字在哈希表中且计数 > 0，则加入结果，并减少计数。

举例（以 nums1 = [4,9,5], nums2 = [9,4,9,8,4] 为例）：

1. 哈希表记录 nums1：{4:1, 9:1, 5:1}。
2. 遍历 nums2：
   • 遇到 9，计数为 1，加入结果，更新哈希表为 {4:1, 9:0, 5:1}。
   • 遇到 4，计数为 1，加入结果，更新为 {4:0, 9:0, 5:1}。
   • 遇到 9，计数为 0，跳过。
   • 遇到 8，不在哈希表，跳过。
   • 遇到 4，计数为 0，跳过。
3. 结果：[9,4]。

复杂度分析：

• 时间复杂度：O(m + n)，其中 m 和 n 为数组长度。
• 空间复杂度：O(min(m, n))。

方法二：排序 + 双指针（适用于已排序或可排序的数组）

核心思想：将两个数组排序后，使用双指针同步遍历，比较元素大小决定移动策略。

步骤：

1. 对两个数组排序。
2. 初始化指针 i 和 j 分别指向两个数组的起始位置。
3. 循环直到任一指针越界：
   • 若 nums1[i] == nums2[j]，加入结果，同时移动 i 和 j。
   • 若 nums1[i] < nums2[j]，移动 i（因为较小元素不可能再匹配）。
   • 若 nums1[i] > nums2[j]，移动 j。

举例（以 nums1 = [4,9,5], nums2 = [9,4,9,8,4] 为例）：

1. 排序：nums1 = [4,5,9], nums2 = [4,4,8,9,9]。
2. 双指针遍历：
   • i=0, j=0：4==4，加入结果，i=1, j=1。
   • i=1, j=1：5<8，移动 i=2。
   • i=2, j=1：9>8，移动 j=2。
   • i=2, j=2：9==9，加入结果，i=3, j=3（越界结束）。
3. 结果：[4,9]。

复杂度分析：

• 时间复杂度：O(m log m + n log n)，主要来自排序。
• 空间复杂度：O(1)（不考虑排序的栈空间）。

方法选择建议

• 若数组已排序，优先用双指针（无需额外空间）。
• 若数组未排序且规模大，用哈希表避免排序开销。
• 若要求结果有序，可用双指针或对哈希表结果排序。

代码实现（哈希表方法）

def intersect(nums1, nums2):
    from collections import defaultdict
    # 总选择较短的数组进行哈希
    if len(nums1) > len(nums2):
        return intersect(nums2, nums1)
    
    count = defaultdict(int)
    for num in nums1:
        count[num] += 1
    
    res = []
    for num in nums2:
        if count[num] > 0:
            res.append(num)
            count[num] -= 1
    return res

通过以上步骤，你可以清晰理解两种解法的适用场景与实现细节。