719 找出第 k 小的距离对（二分查找、双指针）

古城微笑少年丶 2022-09-09 12:44 182阅读 0赞

**1. 问题描述：**

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

**示例 1:**

输入：  
nums = \[1,3,1\]  
k = 1  
输出：0

**解释：**

所有数对如下：  
(1,3) -> 2  
(1,1) -> 0  
(3,1) -> 2  
因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。

**提示:**

2 <= len(nums) <= 10000.  
0 <= nums\[i\] < 1000000.  
1 <= k <= len(nums) \* (len(nums) - 1) / 2.  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-k-th-smallest-pair-distance

**2. 思路分析：**

分析题目可以知道我们可以使用**二分**来枚举数对之间的距离，求解出nums中所有数对之间距离小于等于mid的个数，求解nums中数对之间小于等于mid的个数可以使用**双指针算法**来求解，对于每一个i我们找到最小的j，使得nums\[i\] - nums\[j\] <= mid，这样\[i，j\]之间的数与nums\[i\]的数对之间的距离都是小于等于mid（当指针i往后走不满足条件的时候指针j也一定往后走的所以我们可以使用双指针算法来求解），我们可以枚举出所有的i找到所有满足条件的数对，根据这个结果来更新二分的l和r即可。

![20210901091220579.png][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 计算数对之间绝对值小于等于mid的个数
        def get(self, nums: List[int], mid: int):
            res = 0
            i, j = 0, 0
            # 双指针算法
            while i < len(nums):
                # 找到第一个j使得nums[i] - nums[j] <= mid, 这样[l, r]中的数字与nums[i]的差值肯定是小于等于mid的
                while nums[i] - nums[j] > mid: j += 1
                res += i - j
                i += 1
            return res
    
        def smallestDistancePair(self, nums: List[int], k: int) -> int:
            # 先排序才可以使用双指针算法
            nums.sort()
            l, r = 0, 10 ** 6
            while l < r:
                mid = l + r >> 1
                if self.get(nums, mid) >= k:
                    r = mid
                else:
                    l = mid + 1
            return r

[20210901091220579.png]: /images/20220829/5fd45257f3af47418ebc6f9d01887c9f.png