困难

问题描述

数对 (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.length
• 2 <= n <= 104
• 0 <= nums[i] <= 106
• 1 <= k <= n * (n - 1) / 2

二分查找

首先对数组进行排序，排序后，这个第 $k$ 小的距离必然是在 $[0, num[n-1] - nums[0]]$ 区间范围内，然后在这个区间范围内枚举距离 $d$（范围太大，需要二分枚举），这样问题就转换为：对于距离 $d$ 什么时候是第 $k$ 小的数对距离。

求 $d$ 是第几小的数对距离使用双指针，假设左指针为 $i$，右指针为 $j$，当左指针指向 $nums[i]$ ，右指针往右遍历，取到最大的 $j$, 使得 $nums[j] - nums[i] <= d$，此时，构成的数对个数为 $j - i - 1$，得到的累计结果即为当前 $d$ 所排的位置。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var smallestDistancePair = function (nums, k) {
  nums.sort((a, b) => a - b)
  const n = nums.length
  const check = (t) => {
    let count = 0
    for (let i = 0, j = 1; i < n; i++) {
      while (j < n && nums[j] - nums[i] <= t) j++
      count += j - i - 1
    }
    return count
  }
  let l = 0
  let r = nums[n - 1] - nums[0]
  while (l < r) {
    const mid = (l + r) >> 1
    if (check(mid) >= k) r = mid
    else l = mid + 1
  }
  return l
}

• 时间复杂度：$O(n \times log\,n )$，排序为 $O(n\times log\,n)$，二分查找需要 $O(log\,n)$，双指针需要 $O(n)$。
• 空间复杂度：$O(n \times log\,n)$, 排序所需空间复杂度。