Участник:Plague rat/K-th Smallest Pair Distance

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/find-k-th-smallest-pair-distance/

from bisect import bisect_right
 
class Solution:
    def pairsCount(self, array, val):
        cnt = 0
        for i in range(len(array)):
            cnt += bisect_right(array, array[i] + val, lo=i, hi=len(array)) - (i + 1)
        return cnt
 
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums = sorted(nums)
        _len = len(nums)
 
        left, right = 0, nums[_len - 1] - nums[0]
        while(left < right):
            middle = (left + right) // 2
            if self.pairsCount(nums, middle) < k:
                left = middle + 1
            else:
                right = middle
        return left