[LeetCode][350. Intersection of Two Arrays II] 2 Solutions: Sort with Two Pointers and HashMap

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 2 分钟

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(m \log m + n \log n)\)
  • Space Complexity: \(O(min(m+n))\)

HashMap

Choose the array which is less and use \(\textit{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. 😉😃💗