By Long Luo
This article is the solution 2 Approaches: Sorting with Two Pointers and HashMap of Problem 350. Intersection of Two Arrays II.
Here shows 2 approaches for this problem: Sorting with Two Pointers and HashMap.
Sorting with Two Pointers
Sorting the two arrays first, then find the same elements.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public static int[] intersect_sort(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int len1 = nums1.length;
int len2 = nums2.length;
int[] ans = new int[Math.min(len1, len2)];
int idx = 0;
int p = 0;
int q = 0;
while (p < len1 && q < len2) {
if (nums1[p] == nums2[q]) {
ans[idx++] = nums1[p];
p++;
q++;
} else if (nums1[p] < nums2[q]) {
p++;
} else {
q++;
}
}
return Arrays.copyOfRange(ans, 0, idx);
}
|
Analysis
- Time Complexity: O(mlogm+nlogn)
- Space Complexity: O(min(m+n))
HashMap
Choose the array which is less and use HashMap to store the elements of the array.
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
| public static int[] intersect_sort_hash(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect_sort_hash(nums2, nums1);
}
int len1 = nums1.length;
int len2 = nums2.length;
Map<Integer, Integer> numFreq = new HashMap<>();
for (int i = 0; i < len1; i++) {
numFreq.put(nums1[i], numFreq.getOrDefault(nums1[i], 0) + 1);
}
int[] ans = new int[len1];
int idx = 0;
for (int i = 0; i < len2; i++) {
if (numFreq.containsKey(nums2[i])) {
ans[idx++] = nums2[i];
int freq = numFreq.get(nums2[i]);
if (freq > 1) {
numFreq.put(nums2[i], freq - 1);
} else {
numFreq.remove(nums2[i]);
}
}
}
return Arrays.copyOfRange(ans, 0, idx);
}
|
Analysis
- Time Complexity: O(m+n).
- Space Complexity: O(min(m+n)).
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗