# 793. Find K-th Smallest Pair Distance

### 793. Find K-th Smallest Pair Distance

1. 给定一个数组
2. 计算数组总所有点对的差
3. 求第k大是多少

• 暴力枚举肯定不行
• 换种思路，我们可以二分结果，数组所有点对的差的取值范围是1到最大值-最小值
• 二分结果，计算点对的差小于或等于这个结果有多少个，跟k比是大还是小
• 计算点对的差小于或等于某个值p有多少个，需要遍历数组，对于每个数a，判断数组中有多少个数小于或等于a+p，累加即可
• 复杂度是o(nlogn*logn)

class Solution {
public:
int findIndex(vector<int>& nums, int left, int right, int k) {
while (right - left > 1) {
int mid = (left + right) / 2;
if (nums[mid] <= k) {
left = mid;
} else {
right = mid;
}
}
return left;
}
int judge(vector<int>& nums, int p) {
int ret = 0;
for (int i = 0;i < nums.size();i++) {
ret += findIndex(nums, i, nums.size(), p + nums[i]) - i;
}
return ret;
}
int bsearch(vector<int>& nums, int left, int right, int k) {
left--;
while (right - left > 1) {
int mid = (left + right) / 2;
if (judge(nums, mid) >= k) {
right = mid;
} else {
left = mid;
}
}
return right;
}
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return bsearch(nums, 0, nums[nums.size() - 1] - nums[0], k);
}
};