#leetcode簽到
Day 3
719. Find K-th Smallest Pair Distance
我一開始把距離全取
然後塞進heap TLE...
我以為我很快(X
後來還是偷看答案了
要sort之後走二分搜尋法
2分搜的對象是距離
所以要多生一個新的function去算現在的範圍 (<mid)的 有沒有k個 如果有 mid就是第k個

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        low, high = 0, nums[-1] - nums[0]

        def count_p(m_d):
            cnt, j = 0, 0
            for i in range(n):
                while j < n and nums[j] - nums[i] <= m_d:
                    j += 1
                cnt += j - i - 1
            return cnt

        while low < high:
            mid = (low + high) // 2
            if count_p(mid) < k:
                low = mid + 1
            else:
                high = mid
        return low