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

数对 (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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容