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. 😉😃💗