719. Find K-th Smallest Pair Distance

Link

Solution

只要找到一個最小的差使之滿足:

1. 所有組合(pair)中，他們的差會比這個差小的組合count數<=k

找個方法是透過fast low, 2 pointer去算, fast永遠先到第一個跑出條件的point，再慢慢移動slow pointer去找出滿足條件的區間。 並計算其所累計的組合count數( j -1 -i)

public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        
        int min = 0, max = nums[nums.length-1] - nums[0];
        
        while(max > min){
            int mid = min + (max-min)/2;
            if(enough(nums, mid, k)){
                max = mid;
            }else{
                min = mid+1;
            }
        }
        return min;
    }
    
    public boolean enough(int[] nums, int dist, int k){
        int count = 0;
        int i = 0, j = 0;
        while(i < nums.length){
            
            while(j < nums.length && nums[j] - nums[i] <= dist){
                j++;
            }
            count += j - 1 - i;
            i++;
            
        }
        return count >= k;
    }