【leetcode】719. Find K-th Smallest Pair Distance

题目如下：

解题思路：对于这一类知道上限和下限，求第N位是什么的题目，可以先看看二分查找的方法可不可行。首先对nums进行排序，很显然任意两个元素距离绝对值最小是0，最大是nums[-1] - nums[0]，所以第N小的距离肯定在 0 ~ (nums[-1] - nums[0]) 之间。采用二分查找的话，题目就变成了输入一个数值n，判断是不是第N小的距离。怎么判断n是否是第N小的距离呢？因为nums是有序的，对于nums[i]来说，只要找到(n + nums[i]) 在nums中所处的位置，设为j，那么nums[i] 与下标在[i+1,j]之间的元素的距离均小于n,与在[j+1,len(nums)-1]之间元素距离均大于n，求下标j同样可以采用二分查找。看起来很完美了，但是还有关键的一个地方，(n + nums[i]) 在nums中不一定存在，或者即使存在但是会有多个值。因此需要找到(n + nums[i]) 在nums中所处的左右两个位置的下标，如果两个下标不一样，则表示不存在；下标的差值表示存在多少个(n + nums[i]) 。

代码如下：

class Solution(object):

    def smallestDistancePair(self, nums, k):

        import bisect

        nums.sort()

        low,high = 0, nums[-1] - nums[0]

        while low <= high:

            mid = (low + high) // 2

            less ,equal = 0,0

            for i,v in enumerate(nums):

                left = (bisect.bisect_left(nums,v+mid) - 1 -i)

                less += left

                right = bisect.bisect_right(nums,v+mid) - 1 -i

                equal += (right - left)

            if less >= k:

                high = mid - 1

            elif less + equal < k:

                low = mid + 1

            elif less == k and equal == 0:

                high = mid - 1

            else:

                break

        return mid

巴特西

【leetcode】719. Find K-th Smallest Pair Distance

最新文章

热门文章