Java 3ms beats 95.33% using binary search


  • 0
    W

    The main challenge is to create a binarySearch function that finds the 1st occurrence of a number within range.

    Also we can save the intersection in nums2 instead of creating a new list/dynamic array.
    ...

    public int[] intersect(int[] nums1, int[] nums2) {
    
        if(nums1.length < nums2.length){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int intersectionIndex = 0;
        int startIndex = 0;
        for(int i=0; i<nums2.length; i++){
            int bsIndex = binarySearch1stOccur(nums1, startIndex, nums1.length, nums2[i]);
            if(bsIndex >= 0){
                startIndex = bsIndex + 1;
                nums2[intersectionIndex++] = nums2[i];
            }
        }
        
        return Arrays.copyOf(nums2, intersectionIndex);
    }
    
    public int binarySearch1stOccur(int[] nums, int startIndex, int endIndex, int target){
        int lowIndex = startIndex;
        int highIndex = endIndex-1;
        while(lowIndex <= highIndex){
            int midIndex = lowIndex + (highIndex-lowIndex)/2;
            if(nums[midIndex] < target){
                lowIndex = midIndex+1;
            }else if((nums[midIndex] > target) ||
                      (midIndex>startIndex && nums[midIndex-1]==target)){
                highIndex = midIndex-1;
            }else {
                return midIndex;
            }
        }
        return -1;
    }
    

    ...

    Note that (midIndex>startIndex && nums[midIndex-1]==target) is to ensure that when (nums[midIndex] == target), keep searching until the 1st occurrence of target within range is found


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.