JAVA 5ms Sort + BinarySearch Solution, Shrink Nums2 Size Each Time


  • 0
    Y
    public class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            if(nums1.length == 0 || nums2.length == 0)
                return new int[0];
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            List<Integer> list = new ArrayList<Integer>();
            int left = 0;
            for(int i = 0; i < nums1.length; i++) {
                if(left >= nums2.length)
                    break;
                left = binarySearch(left, nums1[i], nums2);
                if(left < nums2.length && nums1[i] == nums2[left]) {
                    list.add(nums1[i]);
                    left++;
                }
            }
            
            int[] res = new int[list.size()];
            int index = 0;
            for(Integer num: list)
                res[index++] = num;
            return res;
        }
        
        public int binarySearch(int left, int num, int[] nums2) {
            int right = nums2.length - 1;
            while(left < right) {
                int mid = (right - left) / 2 + left;
                if(nums2[left] == num)
                    return left;
                if(nums2[mid] == num) {
                    if(mid - 1 >= left && nums2[mid - 1] == num)
                        right = mid - 1;
                    else
                        return mid;
                }
                else if(nums2[mid] > num)
                    right = mid;
                else
                    left = mid + 1;
            }
            
            return left;
        }
    }

  • 0

    @yrq I am doing this problem almost the same with you, but I got stuck on the binary_search, it seems like it needs to be done a little bit differently, what are you trying to return in the binary search? Thanks in advance


  • 0
    Y

    @vinnie2 said in JAVA 5ms Sort + BinarySearch Solution, Shrink Nums2 Size Each Time:

    binary

    nums1 = [1, 1, 2, 2]
    nums2 = [2, 2]

    left = 0 , current nums2 range from 0 - 1 , left = 0 = binarysearch(), left++;
    left = 1 , current nums2 range from 1 - 1 , left = 1 = binarysearch(), left++;

    each time, binarysearch find nums2[?] == nums1[?] , return the most left position. then change the size of nums2


Log in to reply
 

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