Note:

想到使用三種不同方法去實現

1. Sort & Merge : O(nlogn) +O(1) space

2. HashSet: O(n) + O(n) space

3. Binary Search: O(nlogn) +O(1) space

public class Solution {
    //1. Sort & merge
    /*public int[] intersection(int[] nums1, int[] nums2){
        //corner case
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
            return new int[]{};   
        }

        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0;
        int[] temp = new int[nums1.length];
        int index = 0;
        while( i < nums1.length && j < nums2.length){
            if(nums1[i] == nums2[j]){
                if(index == 0 || temp[index - 1] != nums1[i]){ //
                    temp[index++] = nums1[i];
                }
                i++;
                j++;
            }else if(nums1[i] < nums2[j]){
                i++;
            }else{
                j++;
            }
        }

        int[] ans = new int[index];
        System.arraycopy(temp, 0, ans, 0, index);
        return ans;
    }*/

    //2. Hashset
    /*public int[] intersection(int[] nums1, int[] nums2) {
        //Corner case
        if( nums1 == null || nums2 == null){
            return null;
        }

        HashSet<Integer> set1 = new HashSet<Integer>();
        for(int i = 0; i < nums1.length; i++){
            set1.add(nums1[i]);
        }

        HashSet<Integer> resSet = new HashSet<Integer>();
        for(int i = 0; i < nums2.length; i++){
            if(resSet.contains(nums2[i])){
                continue;            
            }
            //included && avoid duplicated
            if(set1.contains(nums2[i])){
                resSet.add(nums2[i]);
            }
        }

        //HashSet to array
        int[] res = new int[resSet.size()];
        int index = 0;
        for(Integer num : resSet){
            res[index++] = num;
        }

        return res;
    }*/

    //3. Binary search
    //corner case
    public int[] intersection(int[] nums1, int[] nums2){
        //corner case
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
            return new int[]{};
        }

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

        Arrays.sort(nums1);
        for(int i = 0; i < nums2.length; i++){
            if(set.contains(nums2[i])){ //Duplicates skip
                continue;
            }

            if(binarySearch(nums1, nums2[i])){
                set.add(nums2[i]);
            }
        }

        int[] ans = new int[set.size()];
        int index = 0;
        for(Integer num : set){
            ans[index++] = num;
        }
        return ans;
    }

    private boolean binarySearch(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){
                return true;
            }else if(nums[mid] < target){
                start = mid + 1;
            }else{
                end = mid - 1;
            }
        }
        if(nums[start] == target){
            return true;
        }
        if(nums[end] == target){
            return true;
        }
        return false;
    }

}