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