找出第 K 小的数对距离
数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
示例 1：
输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。
示例 2：
输入：nums = [1,1,1], k = 2
输出：0
示例 3：
输入：nums = [1,6,1], k = 3
输出：5
思路
-
排序：
- 首先对数组
nums进行排序。因为在排序后的数组中，数对的距离有一个规律：|nums[i] - nums[j]|（其中i < j）会随着i和j的增大而增大。因此，排序后的数组有助于我们更高效地查找第k小的距离对。
- 首先对数组
-
二分查找：
-
问题是求第
k小的距离，而距离的范围是从0到nums[nums.length - 1] - nums[0]（即排序后的数组中最大值和最小值的差）。 -
我们可以使用二分查找来逼近第 k 小的距离。具体的二分查找目标是：
- 左边界
left：表示最小的距离，即0。 - 右边界
right：表示最大的距离，即nums[nums.length - 1] - nums[0]。 - 通过判断中间的距离
mid，我们可以决定更新二分查找的左右边界，从而逐步找到第k小的距离。
这里把 mid 这个中间距离挑出来的意思是因为，我想要通过统计小于等于 mid 这个中间距离的数对的个数来决定，我这个二分的区间应该怎样去收缩。并且也说明我要写一个用于统计数量的函数，也就是下面的
countPairs - 左边界
-
-
计数函数：
- 对于每一个
mid，我们需要计算所有数对(nums[i], nums[j])，使得|nums[i] - nums[j]| <= mid的数对的数量。我们使用双指针技巧来高效计算这个数量。
- 对于每一个
- 使用指针
i固定一个元素，指针j作为第二个元素，j从i+1开始向右移动，直到nums[j] - nums[i] > mid。 - 在此过程中，
i固定时，所有符合nums[j] - nums[i] <= mid条件的数对(i, j)都是有效的。 countPairs(mid)函数的时间复杂度是O(n)，因为我们只需要一次遍历数组即可。
- 如何更新二分查找的左右边界：
- 如果对于当前的
mid，countPairs(mid)的值小于k，说明当前的mid太小，我们需要增加mid，因此更新左边界left = mid + 1。 - 如果
countPairs(mid)的值大于或等于k，说明当前的mid可能是解或者可以继续缩小，所以更新右边界right = mid。
- 如果对于当前的
import java.util.Arrays;
class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums); // 排序数组
int left = 0, right = nums[nums.length - 1] - nums[0]; // 左右边界初始化
while (left < right) {
int mid = left + (right - left) / 2; // 计算 mid，避免溢出
if (countPairs(nums, mid) < k) {
left = mid + 1; // 如果符合条件的数对小于 k，更新左边界
} else {
right = mid; // 否则更新右边界
}
}
return left; // 最终的 left 即为第 k 小的距离
}
// 计算所有 |nums[i] - nums[j]| <= mid 的数对个数
private int countPairs(int[] nums, int mid) {
int count = 0;
int j = 0;
// 使用双指针技巧
for (int i = 0; i < nums.length; i++) {
// 向右移动 j，直到 nums[j] - nums[i] > mid
while (j < nums.length && nums[j] - nums[i] <= mid) {
j++;
}
// 计算符合条件的数对个数，减去 i 和 i 的情况
count += (j - i - 1);
}
return count;
}
}