給定一個(gè)整數(shù)數(shù)組宪摧，返回所有數(shù)對(duì)之間的第 k 個(gè)最小距離囤捻。一對(duì) (A, B) 的距離被定義為 A 和 B 之間的絕對(duì)差值木柬。
示例 1:
輸入：
nums = [1,3,1]
k = 1
輸出：0
解釋：
所有數(shù)對(duì)如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 個(gè)最小距離的數(shù)對(duì)是 (1,1)役电，它們之間的距離為 0礁阁。
提示:
2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.
C++1
二分法
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int len = nums.size();
// 轉(zhuǎn)化為差
int left = 0, right = nums[len - 1] - nums[0];
while(left < right){
int mid = left + (right - left) / 2;
int count = getCount(nums, mid);
if(count < k)
left = mid + 1;
else
right = mid;
}
return left;
}
//計(jì)數(shù)方式
int getCount(vector<int>& nums, int mid){
int count = 0;
int left = 0;
for(int i = 1; i < nums.size();i++){
while(nums[i] - nums[left] > mid)
left++;
count += i - left;
}
return count;
}
};
