719.找出第K小的数对距离

链接：719.找出第K小的数对距离
难度：Hard
标签：数组、双指针、二分查找、排序
简介：返回 所有数对距离中 第 k 小的数对距离。

题解 1 - cpp

• 编辑时间：2022-06-15
• 执行用时：16ms
• 内存消耗：9.7MB
• 编程语言：cpp
• 解法介绍：排序后，对于每一种差值，计算可能的数量。

class Solution {
   public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), l = 0, r = nums[n - 1] - nums[0], m;
        while (l < r) {
            m = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; i++) cnt += i - bs(nums, i, nums[i] - m);
            if (cnt >= k)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
    int bs(vector<int>& nums, int r, int target) {
        int l = 0, m;
        while (l < r) {
            m = (l + r) >> 1;
            if (nums[m] >= target)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
};