第六章 - 高频考题(困难)
Kth-Pair-Distance

题目地址(822. Kth-Pair-Distance)

题目描述

1
Given a list of integers nums and an integer k, return the k-th (0-indexed) smallest abs(x - y) for every pair of elements (x, y) in nums. Note that (x, y) and (y, x) are considered the same pair.
2
3
Constraints
4
5
n ≤ 100,000 where n is the length of nums
6
Example 1
7
Input
8
nums = [1, 5, 3, 2]
9
k = 3
10
Output
11
2
12
Explanation
13
Here are all the pair distances:
14
15
abs(1 - 5) = 4
16
abs(1 - 3) = 2
17
abs(1 - 2) = 1
18
abs(5 - 3) = 2
19
abs(5 - 2) = 3
20
abs(3 - 2) = 1
21
Sorted in ascending order we have [1, 1, 2, 2, 3, 4].
Copied!

前置知识

  • 排序
  • 二分法

堆(超时)

思路

堆很适合动态求极值。我在堆的专题中也说了,使用固定堆可求第 k 大的或者第 k 小的数。这道题是求第 k 小的绝对值差。于是可将所有决定值差动态加入到大顶堆中,并保持堆的大小为 k 不变。这样堆顶的就是第 k 小的绝对值差啦。
其实也可用小顶堆保存所有的绝对值差,然后弹出 k 次,最后一次弹出的就是第 k 小的绝对值差啦。
可惜的是,不管使用哪种方法都无法通过。

代码

代码支持:Python3
Python3 Code:
1
class Solution:
2
def solve(self, A, k):
3
A.sort()
4
h = [(A[i] - A[i-1], i-1,i) for i in range(1, len(A))]
5
heapq.heapify(h)
6
7
while True:
8
top, i, j = heapq.heappop(h)
9
if not k: return top
10
k -= 1
11
if j + 1 < len(A): heapq.heappush(h, (A[j+1] - A[i], i, j + 1))
Copied!

二分法

思路

这道题是典型的计数二分。
计数二分基本就是求第 k 大(或者第 k 小)的数。其核心思想是找到一个数 x,使得小于等于 x 的数恰好有 k 个。
不能看出,有可能答案不止一个
对应到这道题来说就是找到一个绝对值差 diff,使得绝对值差小于等于 diff 的恰好有 k 个。
这种类型是否可用二分解决的关键在于:
如果小于等于 x 的数恰好有 p 个:
  1. 1.
    p 小于 k,那么可舍弃一半解空间
  2. 2.
    p 大于 k,同样可舍弃一半解空间
等于你看情况放
简单来说,就是让未知世界无机可乘。无论如何我都可以舍弃一半。
回到这道题,如果小于等于 diff 的绝对值差有大于 k 个,那么 diff 有点 大了,也就是说可以舍弃大于等于 diff 的所有值。反之也是类似,具体大家看代码吧。
最后只剩下两个问题:
  • 确定解空间上下界
  • 如果计算小于等于 diff 的有即可
第一个问题:下界是 0 ,下界是 max(nums) - min(min)。
第二个问题:可以使用双指针一次遍历解决。大家可以回忆趁此机会回忆一下双指针。具体地,首先对数组排序,然后使用右指针 j 和 左指针 i。如果 nums[j] - nums[i] 大于 diff,我们收缩 i 直到 nums[j] - nums[i] <= diff。这个时候,我们就可计算出以索引 j 结尾的绝对值差小于等于 diff 的个数,个数就是 j - i。我们可以使用滑动窗口技巧分别计算所有的 j 的个数,并将其累加起来就是答案。

代码

代码支持:Python3
Python3 Code:
1
class Solution:
2
def solve(self, A, k):
3
A.sort()
4
def count_not_greater(diff):
5
i = ans = 0
6
for j in range(1, len(A)):
7
while A[j] - A[i] > diff:
8
i += 1
9
ans += j - i
10
return ans
11
l, r = 0, A[-1] - A[0]
12
13
while l <= r:
14
mid = (l + r) // 2
15
if count_not_greater(mid) > k:
16
r = mid - 1
17
else:
18
l = mid + 1
19
return l
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:由于进行了排序, 因此时间复杂度大约是 $O(nlogn)$
  • 空间复杂度:取决于排序的空间消耗
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。