一、題目
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文章來源：http://www.zghlxwxcb.cn/news/detail-822964.html
二、題解
答案在0到最大差值之間，二分判斷文章來源地址http://www.zghlxwxcb.cn/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的數(shù)對(duì)個(gè)數(shù)
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;
}
};
到了這里，關(guān)于LeetCode719. Find K-th Smallest Pair Distance——二分答案的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
