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

Categories:

题目描述
思路分析
1. 解法一：二分答案 + 双指针计数（推荐）
相似题目

题目描述

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

思路分析

解法一：二分答案 + 双指针计数（推荐）

核心思路：

距离单调：若距离 d 可行，则更大的距离也可行。

对距离进行二分，判断有多少对距离 <= d。

计数用双指针：固定右端点 r，维护最小的 l 使得 nums[r]-nums[l] <= d，累加 r-l。

复杂度分析：

时间复杂度：O(n log W)，其中 n 表示数组长度，W 表示数值范围。

空间复杂度：O(1) 额外空间（排序除外）。

import java.util.Arrays;

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;
    }
}

import "sort"

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
}

相似题目

题目	难度	考察点
378. 有序矩阵中第 K 小的元素	中等	二分答案
1482. 制作 m 束花所需的最少天数	中等	二分答案
410. 分割数组的最大值	困难	二分答案
973. 最接近原点的 K 个点	中等	排序
658. 找到 K 个最接近的元素	中等	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/51681909