719. 找出第 K 小的数对距离-二分查找

719. 找出第 K 小的数对距离-二分查找

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

示例 1：

输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。

示例 2：

输入：nums = [1,1,1], k = 2
输出：0

示例 3：

输入：nums = [1,6,1], k = 3
输出：5

这个题目其实放水了，他的测试数据集，但是防水的原因是，不放水，可能出题人自己都写不出来，解题代码如下：

int cmp(const void* pa, const void* pb) {
    return *(int *)pa - *(int *)pb;
}

int find_index(int *nums,int target,int index,int numsSize){
    int left=index;
    while(abs(nums[left]-nums[index])<=target){
        left++;
        if(left==numsSize){
            break;
        }
    }
     
    return left-index-1;
}

int smallestDistancePair(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int min=0,max=nums[numsSize-1]-nums[0];
    while(min<=max){
        int mid=(min+max)/2;
        int count =0;
        for(int i=0;i<numsSize;i++){
            count=count+find_index(nums,mid,i,numsSize);
        }
      
        if(count>=k){
             max=mid-1;
           
        }
        else{
             min=mid+1;
        }

    }
    
    return min;


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40