【刷题篇】 找出第 K 小的数对距离

一、题目

OJ链接

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-k-th-smallest-pair-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、题解

2.1思路

2.2源码

返回值rightest的初始值设为-1，是为了一种特殊情况，就是给定的nums数组中的数据都是相同的，那么无论给定的K是多少，第K小的距离都是0，进入循环后rightest的值没有改变还是-1，最后返回-1+1=0，符合

    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;
    }