Problem

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

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

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

思路一(hash)

• Time: O(n + m)
• space: O(min(n, m))

    public int[] intersection(int[] nums1, int[] nums2) {
        Map<Integer, Boolean> hash = new HashMap<>();
        for (int n: nums1) {
            hash.put(n, false);
        }

        List<Integer> list = new ArrayList<>();
        for (int n: nums2) {
            if (hash.containsKey(n) && !hash.get(n)) {
                list.add(n);
                hash.put(n, true);
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

思路二(排序 + two pointer)

• time: O(nlogn + mlogm)
• space: O(1)
• 关键是如何避免重复的数加入list中

    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i1 = 0;
        int i2 = 0;
        int index = 0;
        int len1 = nums1.length;
        int len2 = nums2.length;

        List<Integer> list = new ArrayList<>();

        while (i1 < len1 && i2 < len2) {
            if (nums1[i1] < nums2[i2]) {
                i1++;
            } else if (nums1[i1] > nums2[i2]) {
                i2++;
            } else {
                if (list.size() == 0 || nums1[i1] != list.get(list.size() - 1)) {
                    list.add(nums1[i1]);
                }
                i1++;
                i2++;
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

思路三(binary search)

• time: O(nlogn + mlogn), (n << m, 小的拿去排序)
• space: O(1)

    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);

        Set<Integer> set = new HashSet<>();

        for (int n: nums2) {
            if (set.contains(n)) {
                continue;
            }
            int index = Arrays.binarySearch(nums1, n);
            if (index >= 0) {
                set.add(n);
            }
        }
        int[] ans = new int[set.size()];
        int index = 0;
        for (int n: set) {
            ans[index++] = n;
        }

        return ans;
    }