本文共 1360 字，大约阅读时间需要 4 分钟。

1. 问题描述：

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

示例 1:

输入：

提示:

2 <= len(nums) <= 10000.

来源：力扣（LeetCode）

2. 思路分析：

① 其实这道题目比较隐晦，但是仔细分析起来也是存在一些特点的，首先我们从题目中可以得到最小距离与最大距离的，最小距离为0，最大距离为排序之后的首尾元素之差，而我们的想法是在这个范围之内找出第k小的距离，这个就有点像二分查找的模型了，已知了一个最大与最小的范围，我们需要在这个范围之内找到不断缩小范围从而得到正确的答案，对于这道题目来说我们需要通过二分检查当前得到的距离(mid = (l + r) // 2)中在nums的所有数对中是否存在大于等于k个数对使得距离是mid，假如成立我们可以缩小右边界，说明可能存在更小的距离使得数对的距离是等于mid的，假如不成立那么那么将左边界向右扩展一点，最后我们返回l即可

② 本质上还是需要知道这个是一个二分查找的模型，确定左右边界与更新左右边界的策略即可

3. 代码如下：

from typing import Listclass Solution:    def check(self, x, a: List[int], k: int):        res, index = 0, 1        for i in range(len(a)):            j = index            while j < len(a) and a[j] <= a[i] + x:                j += 1            # 记录上一次索引            res += j - i - 1            index = j        return res >= k    def smallestDistancePair(self, nums: List[int], k: int) -> int:        nums.sort()        l, r = 0, nums[- 1] - nums[0]        while l <= r:            mid = (l + r) // 2            if self.check(mid, nums, k):                r = mid - 1            else:                l = mid + 1        return l