LeetCode 719. 找出第 K 小的数对距离

2025-11-18 HGNULB 约 9 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 719. 找出第 K 小的数对距离

题意分析

数组里任意两个下标不同的元素构成一个数对，数对的距离定义为两个值之差的绝对值。把全部 $n(n-1)/2$ 个距离从小到大排好队，题目要的是这一列里第 k 个数。

约束是关键信号：n 最大一万，数对总数量级到五千万，把所有距离真的算出来再排序，时间和内存都会爆掉；而元素值上界只有一百万，也就是说距离本身的取值范围比数对数量小得多。当「答案的取值范围」远小于「答案的候选个数」时，就该考虑在取值范围上做文章而不是在候选集合上做文章。

边界上要注意：数对不区分顺序，且同一个下标不能和自己配对；数组里可以有重复元素，此时距离 0 是合法答案，所以答案的下界是 0 而不是 1；k 从 1 开始计数，不是从 0 开始。

解法：二分答案 + 双指针计数

核心思路

暴力做法是把所有数对的距离全部算出来放进数组再排序，取下标 k - 1 的元素。n 为一万时要生成约五千万个数，$O(n^2 \log n)$ 的时间加 $O(n^2)$ 的空间，直接出局。

瓶颈在于「求第 k 小」被理解成了「必须先把所有候选排好序」。但求第 k 小其实只需要回答一个更弱的问题：给定一个值 d，比 d 小于等于的距离有多少个？如果这个数量第一次达到 k，那么 d 就是答案。

观察到关键的单调性：记 $f(d)$ 为距离不超过 d 的数对个数，d 越大 $f(d)$ 越大，$f$ 是关于 d 的单调不减函数。于是「第 k 小的距离」等价于「使 $f(d) \ge k$ 成立的最小的 d」，这正是一个可以二分的形式。而要快速求 $f(d)$，先把数组排序，固定右端点 r，让左端点 l 是满足 nums[r] - nums[l] <= d 的最小下标，那么以 r 结尾的合法数对恰好有 r - l 个；排序后 nums[r] 单调不减，所以 l 只会单调右移，一趟扫描就能求出 $f(d)$。

二分区间的不变量是：答案始终落在闭区间 [low, high] 内，且 low 之下的所有值都满足 $f < k$、high 处一定满足 $f \ge k$。循环结束时 low 与 high 重合，重合点就是那个最小的可行 d。

解题步骤

先对 nums 升序排序。双指针计数完全建立在「右端点右移时左端点不会左移」这个性质上，而这个性质只有在有序数组上才成立。

确定二分的搜索区间：下界取 0，因为数组允许有重复元素，最小距离可以是 0；上界取 nums[n-1] - nums[0]，它就是最大可能的距离，答案一定不会超过它。

写计数函数 $f(d)$：left 从 0 开始，right 从 0 扫到 n - 1，只要 nums[right] - nums[left] > d 就把 left 右移一格，循环退出后累加 right - left。累加的是 right - left 而不是 right - left + 1，因为下标 right 自己不能和自己配对。

二分主体：取中点 mid，若 $f(\text{mid}) \ge k$ 说明第 k 小的距离不会大于 mid，答案在左半边，令 high = mid（mid 本身仍可能是答案，不能跳过）；否则说明 mid 太小，令 low = mid + 1。

循环条件写成 low < high，退出时两者相等，直接返回 low。这个写法保证了「返回的一定是使条件成立的最小值」，不需要在循环外再做修正。

以 nums = [1, 2, 3, 4]、k = 3 走一遍：排序后仍是 [1, 2, 3, 4]，全部六个距离是 1、2、3、1、2、1，排序后为 1、1、1、2、2、3，第 3 小是 1。二分从 low = 0、high = 4 - 1 = 3 开始。第一轮 mid = 1，计数时 right = 0 得 0 对；right = 1 时 left 仍为 0，累加 1 - 0 = 1，共 1 对；right = 2 时 3 - 1 = 2 > 1，left 移到 1，3 - 2 = 1 满足，累加 2 - 1 = 1，共 2 对；right = 3 时 4 - 2 = 2 > 1，left 移到 2，4 - 3 = 1 满足，累加 3 - 2 = 1，共 3 对。$f(1) = 3 \ge 3$，令 high = 1。第二轮 low = 0、high = 1，mid = 0，计数时 right = 1 处 2 - 1 = 1 > 0，left 移到 1，累加 0；right = 2 处 left 移到 2，累加 0；right = 3 处 left 移到 3，累加 0，总共 $f(0) = 0 < 3$，令 low = 0 + 1 = 1。此时 low = high = 1，循环退出，返回 1，与手算结果一致。

代码实现

// 对距离进行二分，判断有多少对距离 <= d。
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int low = 0;
        int high = nums[nums.length - 1] - nums[0];

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countPairs(nums, mid) >= k) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }

    private int countPairs(int[] nums, int dist) {
        int count = 0;
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            while (nums[right] - nums[left] > dist) {
                left++;
            }
            count += right - left;
        }

        return count;
    }
}

// 对距离进行二分，判断有多少对距离 <= d。
func smallestDistancePair(nums []int, k int) int {
    sort.Ints(nums)
    low := 0
    high := nums[len(nums)-1] - nums[0]

    for low < high {
        mid := low + (high-low)/2
        if countPairs(nums, mid) >= k {
            high = mid
        } else {
            low = mid + 1
        }
    }

    return low
}

func countPairs(nums []int, dist int) int {
    count := 0
    left := 0

    for right := 0; right < len(nums); right++ {
        for nums[right]-nums[left] > dist {
            left++
        }
        count += right - left
    }

    return count
}

复杂度分析

时间复杂度：$O(n \log n + n \log W)$，其中 n 是数组长度，W 是最大距离。排序一次是 $O(n \log n)$；二分在 [0, W] 上进行，迭代 $O(\log W)$ 轮，每轮的双指针计数中 left 与 right 各自只单向走完一遍数组，是 $O(n)$。

空间复杂度：$O(\log n)$，除排序自身的递归栈外只用了几个下标与计数变量，没有开与输入同阶的辅助数组。

关键点总结

当「答案的取值范围」远小于「候选答案的个数」时，就把二分放到值域上而不是放到候选集合上，这是二分答案最核心的判断依据，也是这一整类题的入口。

求第 k 小可以退化成「统计不超过某个值的个数」，因为这个计数函数关于阈值单调不减；把求值问题转成判定问题，是二分答案的通用转换手法。

双指针计数能做到线性，靠的是排序后右端点右移时左端点绝不回退这一单调性；先排序不是为了方便，而是这条性质的前提。

累加 right - left 而不是 right - left + 1，对应「下标自己不能和自己配对」，这类差一细节在计数型二分里最常翻车。

面试视角：面试官通常会先让你说暴力解并估算量级，再追问「五千万个数你打算怎么排序」，这句话就是引导你想到值域二分；主动把 $f(d)$ 的单调性证明一句「d 变大，原来合法的数对仍然合法」，比直接甩答案更能体现你在推导而不是背题。

面试视角：写完后被追问「能不能不排序」是常见后续，答案是可以改用按值域的桶计数配合前缀和，但代价是 $O(W)$ 空间，能把这个权衡讲清楚就够了。

易错点总结

错误写法：忘记先排序就直接进入二分：nums = [3, 1]、k = 1 → 上界被算成 nums[1] - nums[0] = -2，循环一次都不执行，返回 0，而正确答案是 2。

错误写法：二分条件写成 countPairs(mid) > k 才收缩右界：nums = [1, 2, 3, 4]、k = 3 → 收敛到的是第 4 小的距离，返回 2 而不是 1。

错误写法：计数时累加 right - left + 1：nums = [1, 2, 3, 4]、k = 3 → 每个下标都多算了一对自己和自己，$f(0)$ 被算成 4 已经不小于 3，返回 0 而不是 1。

错误写法：左指针的移动条件写成 nums[right] - nums[left] >= dist：nums = [1, 2, 3, 4]、k = 3 → 距离恰好等于 dist 的数对被漏掉，$f(1)$ 被算成 0，二分被推到 2，返回 2 而不是 1。

错误写法：不可行分支写成 low = mid：low = 0、high = 1 且 mid = 0 不可行时 → low 原地不动，low < high 永远成立，死循环直到超时。

错误写法：把 low 初值设成 1，觉得「距离至少是 1」：nums = [1, 1]、k = 1 → 上界是 0 而下界是 1，循环不执行直接返回 1，而正确答案是 0。

错误写法：把 left 指针提到 countPairs 外面声明、跨多轮二分复用：任意需要多轮二分的输入 → 上一轮遗留的 left 位置让本轮计数偏小，二分朝错误方向收缩，返回偏大的距离。

错误写法：把「第 k 小的距离」理解成「第 k 小的不同距离值」，于是去重后再计数：nums = [1, 1, 1]、k = 2 → 三个数对的距离都是 0，去重后只剩一个候选，计数永远达不到 2，二分收敛到上界返回错误结果。

相似题目

题目	难度	考察点
69. x 的平方根	简单	判定函数是一次乘法，重点在整数下界的取舍
410. 分割数组的最大值	困难	判定用贪心分段，统计需要切成几段
644. 子数组最大平均数 II	困难	在实数域二分，判定靠减去均值后的前缀和最小值
668. 乘法表中第k小的数	困难	同为第 k 小，但计数逐行用除法而非双指针
774. 最小化去加油站的最大距离	困难	实数二分，判定统计每段需要补几个加油站
875. 爱吃香蕉的珂珂	中等	判定是向上取整求和，单调方向与本题相反
878. 第 N 个神奇数字	困难	计数靠容斥与最小公倍数，还要取模
1011. 在 D 天内送达包裹的能力	中等	判定要求保序装载，下界受单件最大重量约束
1201. 丑数 III	中等	计数用三元容斥，注意大数溢出
1231. 分享巧克力	困难	最大化最小值，判定统计能切出的最多块数
1482. 制作 m 束花所需的最少天数	中等	在天数上二分，判定扫描连续可用段
1552. 两球之间的磁力	中等	最大化最小间距，判定贪心放球
LCP 12. 小张刷题计划	中等	判定中每天可免除一题，需额外维护段内最大值
LCR 072. x 的平方根	简单	与 69 同题，练习二分边界的收敛写法
LCR 073. 爱吃香蕉的狒狒	中等	与 875 同题，练习速度上界的选取