Day 41 822. Kth-Pair-Distance

822. Kth-Pair-Distance

题目

Given a list of integers nums and an integer k,

return the k-th smallest abs(x - y) for every pair of elements (x, y) in nums.
 
Note that (x, y) and (y, x) are considered the same pair.

Constraints

n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 5, 3, 2]
k = 3
Output
2
Explanation
Here are all the pair distances:

abs(1 - 5) = 4
abs(1 - 3) = 2
abs(1 - 2) = 1
abs(5 - 3) = 2
abs(5 - 2) = 3
abs(3 - 2) = 1
Sorted in ascending order we have [1, 1, 2, 2, 3, 4].

题目思路

• 1、题目为求数组排序之后第 k 大的距离，首先排序数组，最大的距离即为数组头与尾值之差, 最小的距离当然为0，在此范围内去找寻一个合理的值即可。
• 2、使用二分法，每次取 mid = l + (r - l) / 2，可以减少查找的时间复杂度，不然使用计数的话，时间复杂度在O($n^2$)。
• 3、本题目也可以使用数学的思想去考虑，所有的距离对为一共有$n(n-1)$，所以只要大于mid距离的对数有$n(n-1)$ - k，即为不合理。（还是有些东西没想明白，先放着）

class Solution {
public:
    bool isvaild(vector<int>& nums, int dis, int k)
    { 
        int n = nums.size()
        long long int count = 0;
        int i = 0, j = 0;
        while (i < n || j < n)
        {
            while (j < n && nums[j] - nums[i] <= dis) j++;
            count += j - i - 1;
            i++;
        }
        return count >= k;
    };
    
    int solve(vector<int>& nums, int k) {
        int n = nums.size();
        k++;
        sort(nums.begin(), nums.end());
        int l = 0, r = nums[n - 1] - nums[0]; 
        while(l < r) 
        {
            int mid = l + (r - l) / 2;
            int count = 0, left = 0;
            if(isvaild(nums, mid, k)) r = mid;
            else l = mid + 1;
        }
        return l;
}

复杂度

• 时间复杂度：O(nlogn)

• 空间复杂度：O(1)