讨论/《二分查找》 - 找出第 k 小的距离对/
《二分查找》 - 找出第 k 小的距离对
共 2 个回复
class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        if (nums.empty()) 
            return 0;
        sort (nums.begin(), nums.end());
        int left = 0;
        int right = nums[nums.size() - 1] - nums[0];
        while (left < right) {
            int mid = left + (right - left) / 2;
            int l = 0, count = 0;
            for (int i = 0; i < nums.size(); i++){
                while ((nums[i] - nums[l]) > mid)
                    l ++;
                count += (i - l);
                //cout << i << endl;
            }
            if (count < k) 
                left = mid + 1;
            else
                right = mid;
        }
        return left;

    }
};

知道去二分距离,但是不知道如何统计此距离下有多少个数对且时间复杂度O(n)

看了题解才恍然大悟,感觉就是思维问题,也说不清楚思维薄弱在哪,可能还是这种统计的题做少了

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        lo, hi = 0, nums[-1] - nums[0]
        while lo < hi:
            mid = (lo + hi) // 2
            l, count = 0, 0
            for r in range(len(nums)):
                while nums[r] - nums[l] > mid:
                    l += 1
                count += (r - l)
            if count < k: lo = mid + 1
            else: hi = mid
        return lo