友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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
*进阶：*
-
如果给定的数组已经排好序呢？你将如何优化你的算法？
-
如果
nums1的大小比nums2小，哪种方法更优？ -
如果
nums2的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
思路分析
最初思路是分别对两个数组遍历，使用 Map 来统计每个数字出现的次数，然后求交集。其实，只需要对一个数组统计每个数字出现的次数即可，在另外一个数组遍历时，根据次数来判断是否重复。可以介绍一个“取交集”的遍历。
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
* Runtime: 2 ms, faster than 88.63% of Java online submissions for Intersection of Two Arrays II.
*
* Memory Usage: 37 MB, less than 83.87% of Java online submissions for Intersection of Two Arrays II.
*
* Copy from: https://leetcode.com/problems/intersection-of-two-arrays-ii/discuss/82241/AC-solution-using-Java-HashMap/86567[AC solution using Java HashMap - LeetCode Discuss]
*/
public int[] intersect(int[] nums1, int[] nums2) {
if (Objects.isNull(nums1) || nums1.length == 0
|| Objects.isNull(nums2) || nums2.length == 0) {
return new int[0];
}
Arrays.sort(nums1);
Arrays.sort(nums2);
List<Integer> resultList = new ArrayList<>();
int i = 0, j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
resultList.add(nums1[i]);
i++;
j++;
}
}
int[] result = new int[resultList.size()];
for (int k = 0; k < result.length; k++) {
result[k] = resultList.get(k);
}
return result;
}
/**
* Runtime: 4 ms, faster than 24.04% of Java online submissions for Intersection of Two Arrays II.
*
* Memory Usage: 36.8 MB, less than 83.87% of Java online submissions for Intersection of Two Arrays II.
*/
public int[] intersectMap(int[] nums1, int[] nums2) {
if (Objects.isNull(nums1) || nums1.length == 0
|| Objects.isNull(nums2) || nums2.length == 0) {
return new int[0];
}
Map<Integer, Integer> numToCountMap1 = getNumToCountMap(nums1);
// 这个其实没有必要，可以直接循环生成结果List，把原来的count值逐渐减少就好
Map<Integer, Integer> numToCountMap2 = getNumToCountMap(nums2);
Map<Integer, Integer> small, big;
if (numToCountMap1.size() > numToCountMap2.size()) {
big = numToCountMap1;
small = numToCountMap2;
} else {
big = numToCountMap2;
small = numToCountMap1;
}
Map<Integer, Integer> resultMap = new HashMap<>();
int resultLength = 0;
for (Map.Entry<Integer, Integer> entry : small.entrySet()) {
Integer num = entry.getKey();
Integer count = big.getOrDefault(num, 0);
if (count > 0) {
int minCount = Math.min(entry.getValue(), count);
resultMap.put(num, minCount);
resultLength += minCount;
}
}
int[] result = new int[resultLength];
for (Map.Entry<Integer, Integer> entry : resultMap.entrySet()) {
for (int i = 0; i < entry.getValue(); i++) {
result[--resultLength] = entry.getKey();
}
}
return result;
}
private Map<Integer, Integer> getNumToCountMap(int[] nums1) {
Map<Integer, Integer> numToCountMap1 = new HashMap<>();
for (int num : nums1) {
Integer count = numToCountMap1.getOrDefault(num, 0);
numToCountMap1.put(num, ++count);
}
return numToCountMap1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-12 16:40:45
*/
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> numToCnt = new HashMap<>();
for (int i : nums1) {
Integer cnt = numToCnt.getOrDefault(i, 0);
numToCnt.put(i, cnt + 1);
}
List<Integer> result = new ArrayList<>();
for (int i : nums2) {
Integer cnt = numToCnt.getOrDefault(i, 0);
if (cnt > 0) {
result.add(i);
numToCnt.put(i, cnt - 1);
}
}
return result.stream().mapToInt(i -> i).toArray();
}