Fork me on GitHub

719.找出第k小的距离对

发表于 | 分类于 ， | 次阅读
字数统计: 544 | 阅读时长 ≈ 2

基本思路

其实很常规，求第$k$个最小距离，我们已知了最小距离是0（不一定原数组里最小距离为0），最大距离为原数组最后一个元素 - 第一个元素（先排好序）。那么我们就可以用二分法来每次猜一个数，计算小于等于这个数的对数有多少（设为$sum$），然后和$k$比较。

关键是计算$sum$，我们先把原数组拍好序，然后生成$n*n$的矩阵表$v$，其中$v[j][i]$表示第$i$个数 - 第$j$个数，其中$i > j$，如图所示：

1

我们有个序列1 2 3 4 5 6 7，我们用这个序列生成上面的二维表，上面的表其实覆盖了所有的差值，从图中可以看出，这个表同一行是递增的、同一列是递减的（因为前一个数比后一个数大），比如我们想求差小于等于3的个数，那么图中红线以下就是解。

所以思路是：我们遍历每一列（外循环），内循环遍历行，当前的数小于等于目标数时，进入下一列，当前的数大于目标数时，进入下一行。

疑问：为什么要求小于等于目标值而不是小于呢？

如果是要求小于目标值的话，会丢失解，比如差值序列中有相同的数，那么他们的序号相同，且是最小序号，那么就会出现$left = mid + 1$，即直接把范围想右移动了，这样就丢失了目标解。所以我们在求第$k$个的时候，如果有相同的元素，那么我们要求相同元素的最大下标，然后用$right$缩小范围。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin() , nums.end());
        int left = 0;
        int right = nums.back() - nums[0];
        while(left < right){
            int mid = (left + right) / 2;
            int j = 0;
            int sum = 0;
            for(int i = 1 ; i<nums.size() ; ++i){
                for(j ; j < nums.size() ; ++j){
                    if(nums[i] - nums[j] <= mid){
                        break;
                    }
                }
                sum += i - j;
            }
            if(sum >= k) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};