LeetCode 719: Find K-th Smallest Pair Distance

发表于 | | 阅读次数:
字数统计: 481 | 阅读时长 ≈ 2

题目链接

https://leetcode.com/problems/find-k-th-smallest-pair-distance/

题意

给定一个整数数组，返回所有数对之间的第 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。

提示:

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

题目类型

二分

题目分析

对于该类题目，发现k很大的时候，基本也就和二分脱不开干系了。

我们可以注意到，将数组排序后，求出 距离 <= k 的数对个数是非常简单的。

最开始的想法是扫一遍数组，对每个数字加上 k 后加个二分就可以了，二分的时候下一个数字可以直接以上一个数组满足的最大位置作为二分下界再往后分，可以节约很多时间。

由此，我们可以二分最小距离的大小，直至求出答案，具体就见代码了。

对代码需要说明的一点是，二分求出的是满足 <= k 的最大设定距离，因此我们将k - 1， l + 1就能得到正好的第k个最小距离。

时间复杂度

$O(log _{2} (\max(num)-\min(num)) \ast N \ast log _{2} N)$

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int i, n = nums.size(), t;
        sort(nums.begin(), nums.end());
        int m = nums[n - 1] - nums[0];
        int l = -1, r = m + 1, mid, tmp;
        k--;
        while (l < r - 1) {
            mid = (l + r) >> 1;
            tmp = 0;
            for (i = 0; i < n - 1; i++) {
                t = upper_bound(nums.begin(), nums.end(), nums[i] + mid) - nums.begin() - i - 1;
                tmp += t;
            }
            if (tmp <= k)
                l = mid;
            else
                r = mid;
        }
        return l + 1;
    }
};
0%