Description

给出数组\(a[0, n)\),设距离\(d(i, j) = \mid a_i - a_j\mid\),求第\(k\)大距离

Constraints

\(n\)不超过\(10^4\)

Solution

排序然后二分答案,每次猜一个距离

Code

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        std::sort(nums.begin(), nums.end());
        int lo = 0, hi = nums.back() - nums.front();

        auto check = [&](int mid) {
            int count = 0;
            // [l, r)
            for(int l = 0, r = 1; r <= nums.size(); ++r) {
                while(l < r && nums[r-1] - nums[l] > mid) l++;
                count += (r-2) - l + 1;
            }
            return count >= k;
        };
        while(lo < hi) {
            int mid = lo + hi >> 1;
            if(check(mid)) hi = mid;
            else lo = mid+1;
        }
        return lo;
    }
};

LeetCode-719 Find K-th Smallest Pair Distance