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

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节
标签
数组 排序 双指针 二分查找

题目描述

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

image-20260928224550436

image-20260928224550438

题意分析

将所有不同下标数对的绝对差按非递减顺序排列，返回第 k 个距离。相同的元素或距离可以出现多次，每个下标数对都要分别计入，距离 0 也合法。这里只求距离值，不需要返回具体哪一对下标。

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

核心思路

[!blue]

显式生成全部数对需要二次规模的候选。可以改问：给定距离上限 d，有多少数对的距离不超过它？记这个数量为 count(d)，随着 d 增大，合法数对只会增加，因此计数单调不减。

第 k 小距离就是使 count(d) >= k 的最小 d：比它小的阈值容不下前 k 个数对，达到它时才容得下。重复距离会使计数一次增加多个，所以不能要求计数恰好等于 k。

为快速计数，先排序。排序不改变全部数对距离及其出现次数，还让右侧元素减去左侧元素就是绝对差。固定右端 right，不断右移 left，直到 nums[right] - nums[left] <= d。此时下标 [left, right - 1] 都能与 right 配对，更早下标都不满足，贡献恰好为 right - left。

当 right 继续右移，右端值不会变小，原先不合法的左端不可能重新合法，所以 left 不必回退。每个指针最多经过数组一次，单次阈值计数为线性时间。由于 d >= 0，即使没有更早元素可配对，left 到达 right 时差也为 0，扫描会停止。

搜索范围为 [0, 最大值 - 最小值]。若中点计数至少为 k，答案在中点及其左侧，令 high = mid；否则答案严格大于中点，令 low = mid + 1。始终保留答案所在范围，直到两端相遇。

解题步骤

  1. 对输入数组排序，令 low = 0、high = nums[n - 1] - nums[0]。
  2. 当 low < high 时取中点 mid，开始一次独立计数，重置 left = 0。
  3. 逐个移动 right，收缩左端使距离不超过 mid，累计 right - left。
  4. 计数达到 k 就保留中点作为上界，否则令下界越过中点。
  5. 返回相遇位置 low。若所有元素相同，初始上下界都是 0，直接得到答案。

代码实现

// 对距离进行二分，判断有多少对距离 <= 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;

            // 计数达到 k 时仍保留中点，寻找最小可行距离
            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;
    }
}

import "sort"

// 对距离进行二分，判断有多少对距离 <= 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
        // 计数达到 k 时仍保留中点，寻找最小可行距离
        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+1)+n\log(W+1))$，其中 $n$ 为数组长度，$W$ 为最大值与最小值之差。排序一次，每次二分用双指针线性计数。
  • 空间复杂度：二分和计数只使用 $O(1)$ 辅助空间，排序所需空间取决于语言库的具体实现。

关键点总结

[!green]

  • 二分的对象是距离值，判定条件是“不超过它的数对至少有 k 个”。
  • 固定右端后，合法左端形成连续区间，贡献可直接用区间长度计算。
  • 每对下标只在较大的那个下标作为 right 时计入，既不漏计，也不重复。

易错点总结

[!yellow]

  • 写成 right - left + 1 会把当前元素与自身配对；正确计数不包含 right 本身。
  • 搜索下界不能设为 1，重复元素会产生合法的零距离。
  • 收缩条件必须是距离 > d，距离恰好为 d 的数对也应计入。
  • 每次二分计数都要重新初始化左指针，不能沿用上一个阈值的窗口。
  • 本实现会排序输入数组，原元素顺序不会保留。

相似题目

题目 难度 关联与区别
378. 有序矩阵中第 K 小的元素 中等 同样二分答案并统计不超过阈值的对象数量，本题排序后用窗口统计距离合格的数对。
668. 乘法表中第k小的数 困难 两题都在大量隐式候选中查第k小值，关键是低成本实现阈值计数而非生成所有候选。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/51681909
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！