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

这道题到底在问什么

输入

nums1=[4,9,5,9], nums2=[9,4,9,8,4,5]

输出

[9,4,9,5]

最优解：一步一步想明白

1. 3记住口诀：nums1 建计数表，nums2 来配对，配一个扣一个。下面每帧都在套它。
2. 4先把 nums1 做成计数表。现在读到 nums1[0] = 4，下一帧把它的计数加 1。
3. 54 的计数更新成 1。计数表记的是「这个数在 nums1 里还剩几次能配」。
4. 6先把 nums1 做成计数表。现在读到 nums1[1] = 9，下一帧把它的计数加 1。
5. 79 的计数更新成 1。计数表记的是「这个数在 nums1 里还剩几次能配」。
6. 8先把 nums1 做成计数表。现在读到 nums1[2] = 5，下一帧把它的计数加 1。
7. 95 的计数更新成 1。计数表记的是「这个数在 nums1 里还剩几次能配」。
8. 10先把 nums1 做成计数表。现在读到 nums1[3] = 9，下一帧把它的计数加 1。
9. 119 的计数更新成 2。计数表记的是「这个数在 nums1 里还剩几次能配」。
10. 12nums1 的计数表全部建好了。接下来扫 nums2，每个数来表里「认领」名额。
11. 13扫到 nums2[0] = 9，去计数表里查它还剩几个名额：cnt[9] = 2。
12. 14cnt[9] 原来大于 0，说明 nums1 那边还留着一个 9，配上！收进答案，并把 cnt[9] 扣成 1。
13. 15扫到 nums2[1] = 4，去计数表里查它还剩几个名额：cnt[4] = 1。
14. 16cnt[4] 原来大于 0，说明 nums1 那边还留着一个 4，配上！收进答案，并把 cnt[4] 扣成 0。
15. 17扫到 nums2[2] = 9，去计数表里查它还剩几个名额：cnt[9] = 1。
16. 18cnt[9] 原来大于 0，说明 nums1 那边还留着一个 9，配上！收进答案，并把 cnt[9] 扣成 0。
17. 19扫到 nums2[3] = 8，去计数表里查它还剩几个名额：cnt[8] = 0。
18. 20cnt[8] 已经是 0，nums1 那边没有多余的 8 了，跳过这个，不进答案。
19. 21扫到 nums2[4] = 4，去计数表里查它还剩几个名额：cnt[4] = 0。
20. 22cnt[4] 已经是 0，nums1 那边没有多余的 4 了，跳过这个，不进答案。
21. 23扫到 nums2[5] = 5，去计数表里查它还剩几个名额：cnt[5] = 1。
22. 24cnt[5] 原来大于 0，说明 nums1 那边还留着一个 5，配上！收进答案，并把 cnt[5] 扣成 0。
23. 25nums2 全部扫完，答案是 [9,4,9,5]。9 配到 2 个、4 和 5 各 1 个，正好是两边出现次数的较小值。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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();
    }
}

复杂度

面试官可能追问