822. Kth-Pair-Distance#

1
Given a list of integers nums and an integer k,
2

3
return the k-th smallest abs(x - y) for every pair of elements (x, y) in nums.
4

5
Note that (x, y) and (y, x) are considered the same pair.
6

7
Constraints
8

9
n ≤ 100,000 where n is the length of nums
10
Example 1
11
Input
12
nums = [1, 5, 3, 2]
13
k = 3
14
Output
15
2
16
Explanation
17
Here are all the pair distances:
18

19
abs(1 - 5) = 4
20
abs(1 - 3) = 2
21
abs(1 - 2) = 1
22
abs(5 - 3) = 2
23
abs(5 - 2) = 3
24
abs(3 - 2) = 1
25
Sorted in ascending order we have [1, 1, 2, 2, 3, 4].

1
class Solution {
2
public:
3
    bool isvaild(vector<int>& nums, int dis, int k)
4
    {
5
        int n = nums.size();
6
        long long int count = 0;
7
        int i = 0, j = 0;
8
        while (i < n || j < n)
9
        {
10
            while (j < n && nums[j] - nums[i] <= dis) j++;
11
            count += j - i - 1;
12
            i++;
13
        }
14
        return count >= k;
15
    };
16

17
    int solve(vector<int>& nums, int k) {
18
        int n = nums.size();
19
        k++;
20
        sort(nums.begin(), nums.end());
21
        int l = 0, r = nums[n - 1] - nums[0];
22
        while(l < r)
23
        {
24
            int mid = l + (r - l) / 2;
25
            int count = 0, left = 0;
26
            if(isvaild(nums, mid, k)) r = mid;
27
            else l = mid + 1;
28
        }
29
        return l;
30
}