350. 两个数组的交集 II
题目描述
输入两个整数数组 nums1 和 nums2，求它们的交集，但要保留重复。
某个数在 nums1 中出现 a 次、在 nums2 中出现 b 次，那么它在结果中就出现 min(a, b) 次。
以数组形式返回结果，顺序不限。
示例 1
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]
解释：2 在两个数组中都出现 2 次，所以结果有两个 2。
示例 2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]
解释：4 和 9 在 nums1 中各出现 1 次，所以各保留 1 个。
数据范围
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
进阶：如果两个数组已经有序，能怎样优化？如果 nums1 远比 nums2 小，哪种做法更合适？如果 nums2 存在磁盘上、内存放不下，只能分批读入，又该怎么做？
解题思路：排序 + 二分查找
两个数组都排序。按从小到大的顺序取 nums1 的每个 x，在 nums2 的“还没用过的后半段” nums2[p:] 上二分，找第一个 >= x 的位置 j。若 nums2[j] == x，就配对成功，记录 x，并把 p 移到 j+1，表示这个 nums2[j] 已被用掉。因为 x 单调不减，前面用掉的位置以后也不会再需要。
为什么正确
nums2[:p] 中的数要么已被配对，要么小于当前 x，以后都不会再用到。
复杂度分析
时间 O(m log m + n log n)，空间 O(1)（不计返回值）。
易错点
二分的起点必须是 p 而不是 0，否则同一个 nums2[j] 会被重复配对，结果中的次数会多。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
res = []
p = 0
for x in nums1:
j = bisect_left(nums2, x, p)
if j < len(nums2) and nums2[j] == x:
res.append(x)
p = j + 1
return resclass Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
List<Integer> res = new ArrayList<>();
int p = 0;
for (int x : nums1) {
int lo = p, hi = nums2.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (nums2[mid] < x) lo = mid + 1;
else hi = mid;
}
int j = lo;
if (j < nums2.length && nums2[j] == x) {
res.add(x);
p = j + 1;
}
}
return res.stream().mapToInt(Integer::intValue).toArray();
}
}class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector<int> res;
int p = 0;
for (int x : nums1) {
int j = lower_bound(nums2.begin() + p, nums2.end(), x) - nums2.begin();
if (j < (int)nums2.size() && nums2[j] == x) {
res.push_back(x);
p = j + 1;
}
}
return res;
}
};func intersect(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
sort.Ints(nums2)
res := []int{}
p := 0
for _, x := range nums1 {
j := p + sort.SearchInts(nums2[p:], x)
if j < len(nums2) && nums2[j] == x {
res = append(res, x)
p = j + 1
}
}
return res
}var intersect = function(nums1, nums2) {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
const res = [];
let p = 0;
for (const x of nums1) {
let lo = p, hi = nums2.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums2[mid] < x) lo = mid + 1;
else hi = mid;
}
const j = lo;
if (j < nums2.length && nums2[j] === x) {
res.push(x);
p = j + 1;
}
}
return res;
};function intersect(nums1: number[], nums2: number[]): number[] {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
const res: number[] = [];
let p = 0;
for (const x of nums1) {
let lo = p, hi = nums2.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums2[mid] < x) lo = mid + 1;
else hi = mid;
}
const j = lo;
if (j < nums2.length && nums2[j] === x) {
res.push(x);
p = j + 1;
}
}
return res;
}其他解法
哈希表计数是 O(m + n) 时间、O(min(m, n)) 空间；排序做法多一个 log，但几乎不占额外空间，输入已有序时更合适。
解法 2：哈希表计数 时间 O(m + n)，空间 O(min(m, n))
用哈希表统计较短数组中每个数字出现的次数。遍历另一个数组，如果当前数字的计数大于 0，就加入答案并把计数减 1。
线性时间，空间只和较短的数组有关。适合一个数组很小、另一个很大或只能分批读入的情况。如果数组已经有序，排序做法更省空间。
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
cnt = collections.Counter(nums1)
res = []
for x in nums2:
if cnt[x] > 0:
res.append(x)
cnt[x] -= 1
return resclass Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) return intersect(nums2, nums1);
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums1) cnt.merge(x, 1, Integer::sum);
int[] res = new int[nums1.length];
int len = 0;
for (int x : nums2) {
int c = cnt.getOrDefault(x, 0);
if (c > 0) {
res[len++] = x;
cnt.put(x, c - 1);
}
}
return Arrays.copyOf(res, len);
}
}class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) return intersect(nums2, nums1);
unordered_map<int, int> cnt;
for (int x : nums1) cnt[x]++;
vector<int> res;
for (int x : nums2) {
auto it = cnt.find(x);
if (it != cnt.end() && it->second > 0) {
res.push_back(x);
it->second--;
}
}
return res;
}
};func intersect(nums1 []int, nums2 []int) []int {
if len(nums1) > len(nums2) {
nums1, nums2 = nums2, nums1
}
cnt := map[int]int{}
for _, x := range nums1 {
cnt[x]++
}
res := []int{}
for _, x := range nums2 {
if cnt[x] > 0 {
res = append(res, x)
cnt[x]--
}
}
return res
}var intersect = function(nums1, nums2) {
if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];
const cnt = new Map();
for (const x of nums1) cnt.set(x, (cnt.get(x) || 0) + 1);
const res = [];
for (const x of nums2) {
const c = cnt.get(x) || 0;
if (c > 0) {
res.push(x);
cnt.set(x, c - 1);
}
}
return res;
};function intersect(nums1: number[], nums2: number[]): number[] {
if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];
const cnt = new Map<number, number>();
for (const x of nums1) cnt.set(x, (cnt.get(x) ?? 0) + 1);
const res: number[] = [];
for (const x of nums2) {
const c = cnt.get(x) ?? 0;
if (c > 0) {
res.push(x);
cnt.set(x, c - 1);
}
}
return res;
}