lc.719.找出第k小的距离对

​

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

示例 1:

输入：

nums = [1,3,1] k = 1

输出：0 解释： 所有数对如下： (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。

提示:

2 <= len(nums) <= 10000. 0 <= nums[i] < 1000000. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

解题思路

二分法+滑动窗口

我们可以使用双指针来计算出所有小于等于 guess 的距离对数目。我们维护 left 和 right，其中 right 通过循环逐渐递增，left 在每次循环中被维护，使得它满足 nums[right] - nums[left] <= guess 且最小。这样对于 nums[right]，以它为右端的满足距离小于等于 guess 的距离对数目即为 right - left。我们在循环中对这些 right - left 进行累加，就得到了所有小于等于 guess 的距离对数目。

作者：LeetCode 链接：https://leetcode-cn.com/problems/find-k-th-smallest-pair-distance/solution/hei-ming-dan-zhong-de-sui-ji-shu-by-leetcode/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

特殊结论

滑动窗口计算 有序小于k 的对数

1
2
3
4
5
6

int j = 0;//利用滑动窗口， 优化为 o(N) => 总时间复杂度是 o(nLogN)
int less_cnt = 0;
for(int i=1;i<n;i++) {
    while(j<i &&  nums[i] - nums[j] >  mid) ++j; //找到比他小的
    less_cnt += i-j;
}

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:

    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int l = 0,r = nums[n-1] - nums[0];
        // int res = r;
        while(l<r)  {
            int mid = (l+r)/2;
            //判断  mid 是否 是 第 k小的距离对
            int j = 0;//利用滑动窗口， 优化为 o(N) => 总时间复杂度是 o(nLogN)
            int less_cnt = 0;
            for(int i=1;i<n;i++) {
                while(j<i &&  nums[i] - nums[j] >  mid) ++j; //找到比他小的
                less_cnt += i-j;
            }
            if(less_cnt <k) {
                //第k个
                l = mid+1;
            }else {
                r = mid;
                // res = mid;
            }
        }
        return r;
    }
};