讨论/《二分查找》 - 两个数组的交集/
《二分查找》 - 两个数组的交集
共 1 个回复

将数组2排序,遍历数组1在数组2中二分查找,找到的话放入set集合中,利用了set的去重特性,最后把set转换成int数组返回。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums2);
        for(int i = 0; i < nums1.length; i++){
            if(binarySearch(nums2, nums1[i]))
                set.add(nums1[i]);
        }
        int index = 0;
        int[] res = new int[set.size()];
        for(int num : set)
            res[index++] = num;
        return res;
    }

    private boolean binarySearch(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) >>> 1;
            if(target == nums[mid])
                return true;
            else if(target < nums[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        return false;
    }
}