719. 找出第 k 小的距离对

2020-08-25  本文已影响0人  Chiduru

【Description】
给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

示例 1:

输入:
nums = [1,3,1]
k = 1
输出:0
解释:
所有数对如下:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1),它们之间的距离为 0。
提示:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

【Idea】
找第k小的差值对问题,转换成 两数之差<=target 的对数量恰好>=k的最小值(真的好拧巴
找数值对的优化套路,就联想双指针,再联想排序。
同时,假设 target' < target, 对于target对应的差值对<=target的数量,必然>=target'对应的差值对<=target' 的数量。

先从差值查找开始优化,找出差值的范围∈[0, max-min],然后开始二分;
对于每个mid节点,判定mid代表的差值是否满足【差值<=mid】的数对儿数量count>=k,则有:
cnt>=k,则表明mid节点找大了,往小了缩;
cnt<k,表明mid节点找小了, 往大了扩。

为了避免重复计算,这里固定left指针, 只移动right去找在left=固定值时符合条件的数值对,满足nums[right]-nums[left]<=target_sum

hard真的好难, 比着题解看都费老大劲,哭

【Solution】

class Solution:
    # 这里判定当前mid节点处,差值对<=mid的数量>=k的复杂度O(n)很妙
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def possible(guess):
            cnt = left = 0
            for right, x in enumerate(nums):
                while x - nums[left] > guess:
                    left += 1
                cnt += right - left
            return cnt >= k

        nums.sort()
        threshold = nums[-1] - nums[0]
        low = 0
        high = threshold
        while low < high:
            mid = (low+high)//2
            if possible(mid):
                high = mid
            else:
                low = mid+1
        return low
截屏2020-08-25 上午2.03.02.png
上一篇下一篇

猜你喜欢

热点阅读