719. 找出第 k 小的距离对
思路：
首先采用了暴力求差值，11组数据超时，优化后利用map来求，结果在最后的两组超时。。然而还是要用二分写，二分差值，最小的为0，最大的是排完序后最后一个数的值减去第一个数的值，取mid,然后在原来数组里继续二分找有多少对差值cnt是小于等于mid的。
- 若对数cnt大于了k，则说明，mid左边的差值（即差值<=mid的）个数>k,够了，则在mid左边继续寻找，即将右指针为mid
- 若对数cnt小于了k，则说明，mid左边的差值（即差值<=mid的）的个数<k,不够，则在mid的右边继续找，即将左指针为mid+1，
直到找到刚好个数<k的那个mid，最后返回mid+1即可。
一：速度慢的二分，采用lower_bound来求有多少个数对的差值小于mid
class Solution {
public:
bool check(vector<int>& nums,int mid,int k)
{
int cnt=0;
for(int i=0;i<nums.size();i++)
{
int ops=lower_bound(nums.begin(),nums.end(),nums[i]+mid)-(nums.begin()+i);
cnt+=ops-1;
}
return cnt<k;
}
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int L=0,R=nums[nums.size()-1]-nums[0];
while(L<=R)
{
int mid=(L+R)>>1;
if(check(nums,mid,k))
L=mid+1;
else
R=mid-1;
}
return R;
}
};
二：快的二分，采用双指针来求有多少个数对的差值小于mid
class Solution {
public:
bool check(vector<int>& nums,int mid,int k)
{
int cnt=0;
int now=0;
for(int i=0;i<nums.size();i++)
{
while(now<nums.size()&&nums[i]-nums[now]>mid)
now++;
cnt+=(i-now);
}
return cnt<k;
}
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int L=0,R=nums[nums.size()-1]-nums[0];
while(L<R)
{
int mid=(L+R)>>1;
if(check(nums,mid,k))
L=mid+1;
else
R=mid;
}
return L;
}
};