793. Find K-th Smallest Pair Distance
793. Find K-th Smallest Pair Distance
题目: https://leetcode.com/problems/find-k-th-smallest-pair-distance/
难度: Hard
题意：
- 给定一个数组
- 计算数组总所有点对的差
- 求第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);
}
};
