0719. 找出第 K 小的距离对

[giscus[bot]]

0719. 找出第 K 小的距离对

719. 找出第 K 小的距离对 标签：数组、双指针、二分查找、排序 难度：困难 题目链接 0719. 找出第 K 小的距离对 - 力扣 题目大意 描述：给定一个整数数组 nums，对于数组中不同的数 nums[i]、nums[j] 之间的距离定义为 nums[i] 和 nums[j] 的绝对差值，即 dist(nums[i],nums[j])=ab...

https://algo.itcharge.cn/Solutions/0700-0799/find-k-th-smallest-pair-distance/

[701Lee]

c++

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.back() - nums.front();
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            int j = 0;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                while (j < n && nums[j] - nums[i] <= mid) {
                    j++;
                }
                cnt += (j - i - 1);
            }
            if (cnt < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};