very similiar to LC668


  • 0
    Z

    I am not smart enough to work it out though.


  • 0
    T

    looks it is another version of it. it is very similar to leetcode 688

    class Solution {
        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            int low = 0;
            int high = nums[nums.length-1]-nums[0];
            while(low<high){
                int mid=(low+high)>>>1;
                int row = 0;
                int count = 0;
                for(int i=0;i<nums.length;i++){
                    while(nums[i]-nums[row]>mid){
                        row++;
                    }
                    if(i>row){
                        count+=i-row;
                    }
                }
                if(count>=k){
                    high = mid;
                }else{
                    low = mid+1;
                }
            }
            
            return low;
        }
    }
    

  • 0

    @tiandiao123 But why the binary Search result must be one of the distances?


Log in to reply
 

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