Intersection of Two Arrays

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Note:

• Each element in the result must be unique.

• The result can be in any order.

使用二分查找法来做，思路是将一个数组排序，然后遍历另一个数组，把遍历到的每个数字在排序号的数组中用二分查找法搜索，如果能找到则放入结果set中，这里我们用到了set的去重复的特性，

时间复杂度 o(nlogn)

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0)
            return new int[0];
        
        
        Arrays.sort(nums1);
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0 ; i < nums2.length; i++){
            if(binarySearch(nums1,nums2[i])){
                //
                set.add(nums2[i]);
            }
        }
        
        int[] res = new int[set.size()];
        
        int i = 0;
        for(Iterator<Integer> it = set.iterator(); it.hasNext(); ){
            res[i] = it.next();
            i++;
        }
      
        return res;
        
    }
    
    public boolean binarySearch(int[] nums,int target){
        
        int start = 0, end = nums.length - 1;
        
        while(start + 1 < end){
            int mid = start + (end - start)/2;
            
            if(nums[mid] == target){
                return true;
            }
            
            if(nums[mid] > target){
                end = mid;
            }else{
                start = mid;
            }
            
        }
        
        if(nums[start] == target || nums[end] == target){
            return true;
        }
        
        return false;
    }
}

双hashmap 时间复杂度 o(n)

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //一开始不用判断
        
        Map<Integer,Integer> map = new HashMap<>();
        
        for(int i = 0 ; i < nums1.length;i++){
            map.putIfAbsent(nums1[i],1);
        }
        
        Map<Integer,Integer> res = new HashMap<>();
        
        for(int i = 0; i < nums2.length;i++){
            if(map.containsKey(nums2[i]) && !res.containsKey(nums2[i])){
                res.put(nums2[i],1);
            }
        }
        
        int[] result = new int[res.size()];
        
        int index = 0;
        for(int k : res.keySet()){
            result[index++] = k;
        }
            
        
        return result;
            
    }
}