[brush questions] find the number pair distance with the smallest K

One 、 subject

OJ link

Number pair (a,b) By integer a and b form , The number pair distance is defined as a and b The absolute difference between .

Give you an array of integers nums And an integer k , Number pair by nums[i] and nums[j] Constitute and satisfy 0 <= i < j < nums.length . return All pairs of distances The first k Small number pair distance .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/find-k-th-smallest-pair-distance
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Two 、 Answer key

2.1 Ideas

2.2 Source code

Return value rightest The initial value of is set to -1, It's for a special situation , Is the given nums The data in the array is the same , So whatever is given K How much is the , The first K Small distances are 0, After entering the cycle rightest The value of has not changed or -1, Finally back to -1+1=0, accord with

    public static int smallestDistancePair(int[] arr, int k) {
    

            int n=arr.length;
            if(n<2||k<1||k>(n*(n-1))>>1){
    
                  return -1;
        }
        Arrays.sort(arr);
            int left=0;
            int right=arr[n-1]-arr[0];
            int mid=0;
            int rightest=-1;
            while (left<=right){
    
                mid=(left+right)/2;
                if(valid(arr,mid,k)){
    
                    rightest=mid;
                    left=mid+1;
                }else {
    
                    right=mid-1;
                }
            }
            return rightest+1;
    }

    public static boolean valid(int[] arr,int limit,int k){
    

        int x=0;
        for (int l=0,r=1;l<arr.length;r=Math.max(r,++l)){
    
            while (r< arr.length&&(arr[r]-arr[l]<=limit)){
    
                r++;
            }
            x+=r-l-1;
        }
        return x<k;
    }