719. 找出第 k 小的距离对

【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