349. Intersection of Two Arrays

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.

Solution:

Method 1: HashSet

Put all elements from nums1 to the HashSet.

Check every element in nums2.

If it is in the HashSet, this element is an intersection element.

The time complexity is O(n) and the space complexity is O(n);



Code:

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums1) {
            set.add(num);
        }
        HashSet<Integer> intersect = new HashSet<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                intersect.add(num);
            }
        }
        int res[] = new int[intersect.size()];
        int i = 0;
        for (int key : intersect) {
            res[i++] = key;
        }
        return res;
    }
}

Method 2: Two Pointers

Sort two arrays.

Use two pointers from the beginning of two arrays.

Advance one pointer if it points to a smaller number.

If two pointer points to same value elements, this number is an intersection element.

The time complexity is O(nlogn).



Code:

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> intersect = new HashSet<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            }
            else if (nums1[i] > nums2[j]) {
                j++;
            }
            else {
                intersect.add(nums1[i]);
                i++;
                j++;
            }
        }
        i = 0;
        int res[] = new int[intersect.size()];
        for (int key : intersect) {
            res[i++] = key;
        }
        return res;
    }
}

Method 3: Binary Search

Sort one array.

Go through the other array.

For every element, use binary search to check if it is in the sorted array.

The time complexity is O(nlogn).



Code:

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> intersect = new HashSet<>();
        Arrays.sort(nums2);
        for (int num : nums1) {
            if (search(nums2, num)) {
                intersect.add(num);
            }
        }
        int[] res = new int[intersect.size()];
        int i = 0;
        for (int key : intersect) {
            res[i++] = key;
        }
        return res;
    }
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= target) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        return nums[start] == target || nums[end] == target;
    }
}