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

将数组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;
    }
}
3

执行用时:36 ms, 在所有 Python3 提交中击败了93.42%的用户
内存消耗:15 MB, 在所有 Python3 提交中击败了60.45%的用户

class Solution:
    def intersection(self, nums1, nums2):
        if not nums1 or not nums2:
            return []
        length1 = len(nums1)
        length2 = len(nums2)
        short_list, long_list = (nums1, nums2) if length1 <= length2 else (nums2, nums1)
        res = set()
        long_list.sort()
        l = len(long_list)
        for item in set(short_list):
            start, end = 0, l -1
            while start <= end:  
                mid = (start + end) // 2 
                t = long_list[mid]
                if t == item:
                    res.add(item)
                    break
                elif t < item:
                    start = mid + 1
                else:
                    end = mid - 1
        return list(res)