一、题目
The distance of a pair of integers a and b is defined as the absolute difference between a and b.
Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.
Example 1:
Input: nums = [1,3,1], k = 1
Output: 0
Explanation: Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.
Example 2:
Input: nums = [1,1,1], k = 2
Output: 0
Example 3:
Input: nums = [1,6,1], k = 3
Output: 5
Constraints:
n == nums.length
2 <= n <= 104
0 <= nums[i] <= 106
1 <= k <= n * (n - 1) / 2文章来源：https://www.toymoban.com/news/detail-822964.html
二、题解
答案在0到最大差值之间，二分判断文章来源地址https://www.toymoban.com/news/detail-822964.html
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
int n = nums.size();
int res = 0;
sort(nums.begin(),nums.end());
int l = 0,r = nums[n - 1] - nums[0];
while(l <= r){
int mid = l + ((r - l) >> 1);
if(f(nums,mid) >= k){
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
return res;
}
//距离小于limit的数对个数
int f(vector<int>& nums,int limit){
int n = nums.size();
int count = 0;
for(int l = 0,r = 0;l < n;l++){
while(r + 1 < n && nums[r + 1] - nums[l] <= limit) r++;
count += r - l;
}
return count;
}
};
到了这里，关于LeetCode719. Find K-th Smallest Pair Distance——二分答案的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
