Star

LeetCode 349.Intersection of Two Arrays

Posted on | In |

Question

Given two arrays, write a function to compute their intersection.

Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note: Each element in the result must be unique. The result can be in any order.

Explanation

有三种方法可以实现：

  1. 用一个HashMap存起来。Time: O(nlogn) Space: O(n)
  2. 两个数组都排序，然后用两个指针遍历。Time: O(nlogn) Space:O(1)
  3. 排序其中的一个数组，然后用binary search进行搜索。Time: O(nlogn) Space:O(1)

Code

最后一种方法的代码： 

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
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) return intersection(nums2, nums1);
        Arrays.sort(nums2);
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<m; i++) {
            if (binarySearch(nums2, nums1[i])) {
                set.add(nums1[i]);
            }
        }
        int[] result = new int[set.size()];
        int i = 0;
        for (Integer num:set) {
            result[i++] = num;
        }
        return result;
    }
    public boolean binarySearch(int[] nums, int number) {
        int start = 0;
        int end = nums.length-1;
        while (start <= end) {
            int mid = start + (end - start)/2;
            if (nums[mid] == number) return true;
            if (nums[mid] < number) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return false;
    }
}