两个数组的交集 II 图解题解

结果该留几个 9，带重复的交集

给两个数组 nums1、nums2，返回交集，但和普通求交不一样：一个数在两边都出现，结果要保留它在两数组中出现次数的较小值。题面 nums1=[4,9,5,9]、nums2=[9,4,9,8,4,5]，9 在两边各出现 2 次，结果就带 2 个 9；4 和 5 各 1 次，各留 1 个，输出 [9,4,9,5]。

回 nums1 线扫配对，为什么撑不住

拿 nums2 里每个数，回 nums1 从头找一个还没被认领的相同值，配上就把那个位置划掉。nums1 有 n 个数、nums2 有 m 个，每次配对都可能扫遍 nums1，最坏 O(n·m)（大 O 记号，记操作量随规模的放大），两数组一大就吃力。有人想转成集合求交、一行搞定，可去重后 9 只剩一个，丢掉「9 出现两次」这层重复，本题偏要带重复，也不对。

只要知道每个数还剩几个能配

慢就慢在每次都回 nums1 线扫，其实只要知道 nums1 里每个数还剩几个能配就够了。把 nums1 过一遍，用一张计数表（哈希表，键是数值、值是它在 nums1 出现的次数）记下每个数出现几次。为什么记次数、不只记「出现过」——交集要保留较小的出现次数，9 在 nums1 有 2 个，最多配出 2 个 9；只记「出现过」等于把次数拍成 1，多出来那个 9 就配不上。

扫 nums2 配一个、扣一个名额

接着扫 nums2，每个数 x 查 cnt[x]：大于 0 说明 nums1 还留着一个没配的 x，收进答案，再把 cnt[x] 减 1，用掉一个名额；等于 0 说明没有或已配完，跳过不收。减 1 是重复次数不出错的关键——收一个扣一个，同一个 x 在 nums2 出现多次时，只能配到 nums1 里剩的那几个，扣光就再也配不上。扫完 nums2 就得到答案。

nums1=[4,9,5,9] 配 nums2，逐个查表

拿 nums1=[4,9,5,9]、nums2=[9,4,9,8,4,5] 走一遍。先建表：扫 nums1 得 cnt={4:1, 9:2, 5:1}。再扫 nums2。第一个 9，cnt[9]=2>0，收下、cnt[9] 减成 1。第二个 4，cnt[4]=1>0，收下、cnt[4] 减成 0。第三个 9，cnt[9]=1>0，收下、cnt[9] 减成 0。第四个 8，cnt[8]=0，跳过；第五个 4，cnt[4] 已是 0，跳过。第六个 5，cnt[5]=1>0，收下、cnt[5] 减成 0。答案 [9,4,9,5]：9 配 2 个、4 和 5 各 1 个，正是两边较小的出现次数。

减 1 那步漏掉，重复的数被反复领走

建表扫 nums1、配对扫 nums2，两趟都是线性，时间 O(n+m)；计数表只装 nums1 出现过的数，空间 O(n)。配对后漏了 cnt[x] 减 1，同一个名额会被 nums2 里重复的数反复领走，答案多出一堆重复。用集合去重再求交能糊弄过「交集 I」，这题会把重复全抹平、9 只剩一个。边界先想清：两数组毫无公共值时答案为空；有一个数组为空时交集必空；两数组相同时结果就是整份数组。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        cnt = Counter(nums1)
        ans = []
        for x in nums2:
            if cnt[x]:
                ans.append(x)
                cnt[x] -= 1
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> cnt;
        for (int x : nums1) {
            ++cnt[x];
        }
        vector<int> ans;
        for (int x : nums2) {
            if (cnt[x]-- > 0) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int[] cnt = new int[1001];
        for (int x : nums1) {
            ++cnt[x];
        }
        List<Integer> ans = new ArrayList<>();
        for (int x : nums2) {
            if (cnt[x]-- > 0) {
                ans.add(x);
            }
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}