题目描述
给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
样例
输入:
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
.
算法
(二分,双指针) $O(n \log n)$
- 显然我们可以采用二分确定第 $k$ 小的数对的值是多少。
- 给定一个候选值
mid
,我们可以通过双指针算法,在线性时间内求出小于等于mid
的数对有多少个。 - 我们采用标准的二分模板,每次将区间分为
[l, mid]
和[mid + 1, r]
,然后求出小于等于mid
的数对的个数t
。当且仅当k <= t
,答案在[l, mid]
的区间中。
时间复杂度
- 二分的时间复杂度为 $O(\log n)$,每次判定需要 $O(n)$ 的时间,故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 仅适用常数个变量,故空间复杂度为 $O(1)$。
C++ 代码
class Solution {
public:
int get_less_than_equal(const vector<int>& nums, int mid) {
int n = nums.size();
int tot = 0;
for (int i = 1, j = 0; i < n; i++) {
while (j < i && nums[i] - nums[j] > mid)
j++;
tot += i - j;
}
return tot;
}
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int l = 0, r = nums.back() - nums[0];
while (l < r) {
int mid = (l + r) >> 1;
if (k <= get_less_than_equal(nums, mid))
r = mid;
else
l = mid + 1;
}
return l;
}
};
alternative implementation