友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
350. Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]Note:
-
Each element in the result should appear as many times as it shows in both arrays.
-
The result can be in any order.
Follow up:
-
What if the given array is already sorted? How would you optimize your algorithm?
-
What if nums1's size is small compared to nums2's size? Which algorithm is better?
-
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
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;
}