数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

示例 1：

输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。

示例 2：

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

示例 3：

输入：nums = [1,6,1], k = 3
输出：5

提示：

• n == nums.length
• 2 <= n <= 10^4
• 0 <= nums[i] <= 10^6
• 1 <= k <= n * (n - 1) / 2

思路

• 由于数组的长度范围很大，所以需要考虑使用二分法
• 给定距离 mid，计算所有距离小于等于 mid 的数对数目 cnt 可以使用双指针：初始左端点 i = 0，我们从小到大枚举所有数对的右端点 j，移动左端点直到 nums[j]−nums[i]≤mid，那么右端点为 j 且距离小于等于 mid 的数对数目为 j−i，计算这些数目之和。

方法一：排序 + 二分法 + 双指针

public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, right = nums[nums.length - 1] - nums[0], ans = 0;
        while (left <= right) {
            int mid = (right + left) / 2;
            int cnt = 0;
            for (int i = 0, j = 0; j < nums.length; j++) {
                while (nums[j] - nums[i] > mid) {
                    i++;
                }
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

正常双重遍历 + 优先队列（内存超出限制）

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                queue.add(Math.abs(nums[i] - nums[j]));
            }
        }
        int ans = -1;
        while (k > 0 && !queue.isEmpty()) {
            ans = queue.poll();
            k--;
        }
        return ans;
    }
}

这种写法，仅供参考，在leetcode上通不过。报内存超出限制

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/find-k-th-smallest-pair-distance/solution/zhao-chu-di-k-xiao-de-shu-dui-ju-chi-by-xwfgf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。