0719：找出第 K 小的数对距离（★★）

力扣第 719 题

题目

数对 (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

相似问题：

• 0373：查找和最小的 K 对数字
• 0378：有序矩阵中第 K 小的元素
• 0658：找到 K 个最接近的元素
• 0668：乘法表中第k小的数
• 0786：第 K 个最小的质数分数（2168 分）
• 3134：找出唯一性数组的中位数（2451 分）

分析

典型的二分问题，固定距离 a，计算 <=a 的距离个数即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def cal(a):
            res = 0
            for j,y in enumerate(A):
                i = bisect_left(A,y-a)
                res += j-i
            return res
        A = sorted(nums)
        return bisect_left(range(A[-1]-A[0]),k,key=cal)

58 ms