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

[giscus[bot]]

0719. 找出第 K 小的数对距离 | 算法通关手册

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