349. Intersection of Two Arrays.java

求交集，结果中不重复
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.
//hashset存第一个数组的所有元素，然后检查第二数组。一样的，set中remove，加入arraylist。最后从arraylist腾到int[]  
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set=new HashSet<>();
        ArrayList<Integer> arr=new ArrayList<>();
        for(int num:nums1) set.add(num);
        for(int num:nums2){
            if(set.contains(num)){
                set.remove(num);
                arr.add(num);
            }
        }
        int k=0;
        int[] res=new int[arr.size()];
        for(Integer num: arr){
            res[k++]=num;
        }
        return res;
    }
}

如果已经是sorted的数组了，如何优化？
// two pointers（分别从2个数组的头开始比较，移动）

如果nums1的长度比nums2小? Which algorithm is better?
// 在nums1上使用hash，扫描nums2, 时间长，空间小
// 在nums2 上使用hash，扫描nums1, 时间少，空间大
// sorted数组，可以使用binary search在nums2

 What if elements of nums2 are stored on disk, and memory is limited so that you can't load all elements into memory at once?
如果nums2已经排好序在磁盘，空间是有限的，不能一次load所有元素？
// 1.binary search on nums1 (sort it first)
// 2.或者hash on nums1 (need space)

下面可以不看，是具体实现
// 具体：1. Sort & Binary Search 对其中一个
//O(mlogn) time ，O(n) space
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return new int[]{};
        }
        HashSet<Integer> set = new HashSet<>();
        Arrays.sort(nums1);   //nums1排序
        for (int i : nums2) { 
            if (!set.contains(i) && binarySearch(nums1, i)) {  //在nums1中寻找每一个nums2的元素
                set.add(i);
            }
        }
        int[] res = new int[set.size()];
        int i = 0;
        for (int num : set) {
            res[i++] = num;//remember to i++ !!!
        }
        return res;
    }
    
    private boolean binarySearch(int[] a, int target) {
        if (a == null || a.length == 0) {
            return false;
        }
        int start = 0;
        int end = a.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (a[mid] == target) {
                return true;
            } else if (a[mid] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (a[start] == target || a[end] == target) {
            return true;
        }
        return false;
    }
}
//具体2: 2pointers
public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return new int[]{};
        }
        ArrayList<Integer> list = new ArrayList<>();//you can use hashset here as well
        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 {
                if (list.size() == 0 || list.get(list.size() - 1) != nums1[i]) {
                    list.add(nums1[i]);
                }
                i++;
                j++;
            }
        }
        int[] res = new int[list.size()];
        for (int k = 0; k < list.size(); k++) {
            res[k] = list.get(k);
        }
        return res;
    }
}