跳至主要內容

0719. 找出第 k 小的距离对

ITCharge大约 2 分钟

0719. 找出第 k 小的距离对open in new window

  • 标签:数组、双指针、二分查找、排序
  • 难度:困难

题目链接

题目大意

描述:给定一个整数数组 numsnums,对于数组中不同的数 nums[i]nums[i]nums[j]nums[j] 之间的距离定义为 nums[i]nums[i]nums[j]nums[j] 的绝对差值,即 dist(nums[i],nums[j])=abs(nums[i]nums[j])dist(nums[i], nums[j]) = abs(nums[i] - nums[j])

要求:求所有数对之间第 kk 个最小距离。

说明

  • n==nums.lengthn == nums.length
  • 2n1042 \le n \le 10^4
  • 0nums[i]1060 \le nums[i] \le 10^6
  • 1kn×(n1)/21 \le k \le n \times (n - 1) / 2

示例

  • 示例 1:
输入:nums = [1,3,1], k = 1
输出:0
解释:数对和对应的距离如下:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ,距离为 0
  • 示例 2:
输入:nums = [1,1,1], k = 2
输出:0

解题思路

思路 1:二分查找算法

一般来说 topK 问题都可以用堆排序来解决。但是这道题使用堆排序超时了。所以需要换其他方法。

先来考虑第 kk 个最小距离的范围。这个范围一定在 [0,max(nums)min(nums)][0, max(nums) - min(nums)] 之间。

我们可以对 numsnums 先进行排序,然后得到最小距离为 00,最大距离为 nums[1]nums[0]nums[-1] - nums[0]。我们可以在这个区间上进行二分,对于二分的位置 midmid,统计距离小于等于 midmid 的距离对数,并根据它和 kk 的关系调整区间上下界。

统计对数可以使用双指针来计算出所有小于等于 midmid 的距离对数目。

  1. 维护两个指针 leftleftrightrightleftleftrightright 都指向数组开头位置。
  2. 然后不断移动 rightright,计算 nums[right]nums[right]nums[left]nums[left] 之间的距离。
  3. 如果大于 midmid,则 leftleft 向右移动,直到距离小于等于 midmid 时,统计当前距离对数为 rightleftright - left
  4. 最终将这些符合要求的距离对数累加,就得到了所有小于等于 midmid 的距离对数目。

思路 1:代码

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def get_count(dist):
            left, count = 0, 0
            for right in range(1, len(nums)):
                while nums[right] - nums[left] > dist:
                    left += 1
                count += (right - left)
            return count

        nums.sort()
        left, right = 0, nums[-1] - nums[0]
        while left < right:
            mid = left + (right - left) // 2
            if get_count(mid) >= k:
                right = mid
            else:
                left = mid + 1
        return left

思路 1:复杂度分析

  • 时间复杂度O(n×logn)O(n \times \log n),其中 nn 为数组 numsnums 中的元素个数。
  • 空间复杂度O(logn)O(\log n),排序算法所用到的空间复杂度为 O(logn)O(\log n)