难度: Hard
数对 (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
提示：
n == nums.length2 <= n <= 1040 <= nums[i] <= 1061 <= k <= n * (n - 1) / 2运行时间: 50 ms
内存: 16.7 MB
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
def count(mid: int) -> int:
cnt = i = 0
for j, num in enumerate(nums):
while num - nums[i] > mid:
i += 1
cnt += j - i
return cnt
nums.sort()
return bisect_left(range(nums[-1] - nums[0]), k, key=count)
这个题解使用了二分查找的思路。首先将数组 nums 排序，然后二分枚举可能的距离值 mid，统计所有距离小于等于 mid 的数对数量 cnt。如果 cnt >= k，说明第 k 小的距离一定不超过 mid，我们可以缩小上界；否则我们需要增大下界。最后二分出第 k 小的距离。
时间复杂度: O(nlog(n+D))
空间复杂度: O(logn)
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
def count(mid: int) -> int:
cnt = i = 0
for j, num in enumerate(nums):
while num - nums[i] > mid:
i += 1
cnt += j - i
return cnt
nums.sort() # 对数组进行排序
# 使用二分查找寻找第 k 小的距离
return bisect_left(range(nums[-1] - nums[0]), k, key=count)
考虑到数对距离的值域是有序的（最小的距离是0，最大的距离是数组中最大值与最小值之差），并且当我们知道有k个数对的距离小于等于某个值时，可以推断出第k小的数对距离不会超过这个值。这个性质使得我们可以使用二分查找在有序的值域内快速逼近第k小的距离，因为我们可以通过统计操作来验证每一个'猜测'是否合理，从而高效地缩小搜索范围。
函数`count(mid: int)`通过遍历排序后的数组，并使用双指针技术统计每个元素作为数对较大数时，与之前元素的差不超过`mid`的数量。具体实现中，外层循环固定较大数`num`，内层循环的指针`i`移动直到`num - nums[i]`大于`mid`为止，此时`[i, j)`的所有数与`num`的差都不超过`mid`，通过`j - i`计算这些数对的数量，累加得到总的符合条件的数对数量。
在排序后的数组中，`nums[-1] - nums[0]`即是数组中最大值与最小值的差，代表了可能的最大数对距离。由于数对距离的定义（任意两数的绝对差值），任何两数的差值都不会超过这个最大差值。因此，使用`nums[-1] - nums[0]`作为上界是合理的，它确保了覆盖所有可能的数对距离，避免遗漏，同时也没有不必要地扩大搜索范围。
该`while`循环通过移动指针`i`来排除那些与`num`的差值超过`mid`的数对。这样，每次外层循环迭代到新的`num`时，内层循环不需要从头开始计算，而是从上一次的`i`位置继续，避免了重复的比较和计算。这种方法称为双指针或滑动窗口技术，大大提升了函数的效率，使其能在较大的数据集上运行得更快。