【Description】
給定一個(gè)整數(shù)數(shù)組逗概，返回所有數(shù)對(duì)之間的第 k 個(gè)最小距離。一對(duì) (A, B) 的距離被定義為 A 和 B 之間的絕對(duì)差值拆祈。
示例 1:
輸入：
nums = [1,3,1]
k = 1
輸出：0
解釋：
所有數(shù)對(duì)如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 個(gè)最小距離的數(shù)對(duì)是 (1,1)，它們之間的距離為 0。
提示:
2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.
【Idea】
找第k小的差值對(duì)問(wèn)題舌劳，轉(zhuǎn)換成 兩數(shù)之差<=target 的對(duì)數(shù)量恰好>=k的最小值（真的好擰巴
找數(shù)值對(duì)的優(yōu)化套路，就聯(lián)想雙指針玫荣，再聯(lián)想排序甚淡。
同時(shí)，假設(shè) target' < target, 對(duì)于target對(duì)應(yīng)的差值對(duì)<=target的數(shù)量捅厂，必然>=target'對(duì)應(yīng)的差值對(duì)<=target' 的數(shù)量贯卦。
先從差值查找開(kāi)始優(yōu)化资柔，找出差值的范圍∈[0, max-min]，然后開(kāi)始二分撵割；
對(duì)于每個(gè)mid節(jié)點(diǎn)贿堰，判定mid代表的差值是否滿足【差值<=mid】的數(shù)對(duì)兒數(shù)量count>=k，則有：
cnt>=k啡彬，則表明mid節(jié)點(diǎn)找大了羹与，往小了縮；
cnt<k庶灿，表明mid節(jié)點(diǎn)找小了纵搁， 往大了擴(kuò)。
為了避免重復(fù)計(jì)算往踢，這里固定left指針腾誉， 只移動(dòng)right去找在left=固定值時(shí)符合條件的數(shù)值對(duì)，滿足nums[right]-nums[left]<=target_sum
hard真的好難峻呕， 比著題解看都費(fèi)老大勁妄辩，哭
【Solution】
class Solution:
# 這里判定當(dāng)前mid節(jié)點(diǎn)處，差值對(duì)<=mid的數(shù)量>=k的復(fù)雜度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
