binary-search - Leetcode 719. 找到第 K 个最小的对距离

Question

问题陈述如下 - 给定一个整数数组，返回所有对中的第 k 个最小距离。一对 (A, B) 的距离定义为 A 和 B 之间的绝对差。

leetcode 接受的解决方案是 Binary Search + Prefix Sum Approach。但即使经历了100多次，我也无法弄清楚。

有人可以指导我吗？可能通过一个示例的空运行帮助我弄清楚我们是如何使用二分搜索实际消除搜索空间的？请帮我举个例子，因为互联网上有大量的描述性解释

Answer 1

这是一个 LeetCode 硬标记问题，您可以在此链接中查看各种解决方案的说明：

Python

class Solution:
    def smallestDistancePair(self, nums, k):
        def count(arr, val):
            res = 0
            for i in range(len(arr)):
                res += bisect.bisect_right(arr, arr[i] + val, lo=i) - i - 1
            return res

        nums.sort()
        lo = min(abs(nums[i] - nums[i + 1]) for i in range(len(nums) - 1))
        hi = abs(nums[0] - nums[~0])
        while lo < hi:
            mid = (lo + hi) // 2
            if count(nums, mid) < k:
                lo = mid + 1
            else:
                hi = mid
        return lo

爪哇

class Solution {
    private int upperBound(int[] nums, int lo, int hi, int key) {
        if (nums[hi] <= key)
            return hi + 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (key >= nums[mid])
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }

    private int countPairs(int[] nums, int mid) {
        int length = nums.length;
        int res = 0;
        for (int i = 0; i < length; i++)
            res += upperBound(nums, i, length - 1, nums[i] + mid) - i - 1;
        return res;
    }

    public int smallestDistancePair(int[] nums, int k) {
        int length = nums.length;
        Arrays.sort(nums);
        int lo = nums[1] - nums[0];
        for (int i = 1; i < length - 1; i++)
            lo = Math.min(lo, nums[i + 1] - nums[i]);

        int hi = nums[length - 1] - nums[0];

        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (countPairs(nums, mid) < k)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
}

C++

#include <vector>
#include <algorithm>

static const struct Solution {
    static const int smallestDistancePair(
        const std::vector<int> &nums, 
        const int k
    ) {
        std::vector<int> copy_nums = nums;
        std::sort(copy_nums.begin(), copy_nums.end());
        const int length = copy_nums.size();
        int lo = 0;
        int hi = 1e6;

        while (lo < hi) {
            const int mid = lo + (hi - lo) / 2;
            int count = 0;

            for (int i = 0, j = 0; i < length; i++) {
                while (j < length and copy_nums[j] - copy_nums[i] <= mid) {
                    j++;
                }

                count += j - i - 1;
            }

            if (count < k) {
                lo = mid + 1;

            } else {
                hi = mid;
            }
        }

        return lo;
    }
};