加载中...
719-找出第 k 小的距离对(Find K-th Smallest Pair Distance)
发表于:2021-12-03 | 分类: 困难
字数统计: 2.2k | 阅读时长: 10分钟 | 阅读量:

原文链接: https://leetcode-cn.com/problems/find-k-th-smallest-pair-distance

英文原文

The distance of a pair of integers a and b is defined as the absolute difference between a and b.

Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.

 

Example 1:

Input: nums = [1,3,1], k = 1
Output: 0
Explanation: Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.

Example 2:

Input: nums = [1,1,1], k = 2
Output: 0

Example 3:

Input: nums = [1,6,1], k = 3
Output: 5

 

Constraints:

  • n == nums.length
  • 2 <= n <= 104
  • 0 <= nums[i] <= 106
  • 1 <= k <= n * (n - 1) / 2

中文题目

给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

示例 1:

输入:
nums = [1,3,1]
k = 1
输出:0 
解释:
所有数对如下:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1),它们之间的距离为 0。

提示:

  1. 2 <= len(nums) <= 10000.
  2. 0 <= nums[i] < 1000000.
  3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

通过代码

官方题解

方法一:堆 [超出时间限制]

使用堆可以帮我们找到第 k 小值。我们将数组排序,此时对于固定的下标 i,从小到大的距离分别为 (i, i + 1)(i, i + 2),…,(i, N - 1)。因为 (i, j + 1) 的距离不会小于 (i, j),因此如果 (i, j) 还在堆中,我们没有必要把 (i, j + 1) 放入堆中。

因此,我们首先将所有 (i, i + 1) 放入堆中,即 heap = [(i, i + 1) for all i]。每次取出堆中的最小元素 (i, j) 时(元素的大小为 nums[j] - nums[i],即距离),再把 (i, j + 1) 放入堆中。直到取出 k 个元素,就得到了第 k 小的距离。

[sol1]
class Solution(object): def smallestDistancePair(self, nums, k): nums.sort() heap = [(nums[i+1] - nums[i], i, i+1) for i in xrange(len(nums) - 1)] heapq.heapify(heap) for _ in xrange(k): d, root, nei = heapq.heappop(heap) if nei + 1 < len(nums): heapq.heappush((nums[nei + 1] - nums[root], root, nei + 1)) return d
[sol1]
class Solution { public int smallestDistancePair(int[] nums, int k) { Arrays.sort(nums); PriorityQueue<Node> heap = new PriorityQueue<Node>(nums.length, Comparator.<Node> comparingInt(node -> nums[node.nei] - nums[node.root])); for (int i = 0; i + 1 < nums.length; ++i) { heap.offer(new Node(i, i+1)); } Node node = null; for (; k > 0; --k) { node = heap.poll(); if (node.nei + 1 < nums.length) { heap.offer(new Node(node.root, node.nei + 1)); } } return nums[node.nei] - nums[node.root]; } } class Node { int root; int nei; Node(int r, int n) { root = r; nei = n; } }

复杂度分析

  • 时间复杂度:$O((k + N) \log N)$,其中 $N$ 为 nums 数组的长度。因为 k 最大可以达到 O(N^2),因此最坏情况下,时间复杂度为 $O(N^2 \log N)$,超出了时间限制。

  • 空间复杂度:$O(N)$。堆中的元素个数是 $O(N)$ 的。

方法二:二分查找 + 前缀和

分析

由于第 k 小的距离一定在 [0, W = max(nums) - min(nums)] 中,我们在这个区间上进行二分。对于当前二分的位置 guess,统计距离小于等于 guess 的距离对数量,并根据它和 k 的关系调整区间的上下界。

我们定义函数 possible(guess) 为真,当且仅当距离小于等于 guess 的距离对数量比 k 大或和 k 相等。

算法

我们用 prefix[v] 表示 nums 数组中比 v 小或者和 v 相等的元素个数,用 multiplicity[j] 表示满足 i < jnums[i] == nums[j]i 的个数。这两个数组都可以通过对 nums 线性扫描得到。

此时,对于每一个固定的 i,满足 i < jnums[j] - nums[i] <= guessj 的个数为 prefix[x + guess] - prefix[x] + count[i] - multiplicity[i],其中 x = nums[i]count[i] 表示 nums[i] 在数组中出现的次数。我们遍历所有的 i 并对上式求和,就得到了所有小于等于 guess 的距离对数目。

此外,由于所有 count[i] - multiplicity[i] 的和与 multiplicity[i] 的和实际上是相等的,在求和时,我们可以把前者替换为后者(但并不会改变时间复杂度)。

[sol1]
class Solution(object): def smallestDistancePair(self, nums, k): def possible(guess): #Is there k or more pairs with distance <= guess? return sum(prefix[min(x + guess, W)] - prefix[x] + multiplicity[i] for i, x in enumerate(nums)) >= k nums.sort() W = nums[-1] #multiplicity[i] = number of nums[j] == nums[i] (j < i) multiplicity = [0] * len(nums) for i, x in enumerate(nums): if i and x == nums[i-1]: multiplicity[i] = 1 + multiplicity[i - 1] #prefix[v] = number of values <= v prefix = [0] * (W + 1) left = 0 for i in xrange(len(prefix)): while left < len(nums) and nums[left] == i: left += 1 prefix[i] = left lo = 0 hi = nums[-1] - nums[0] while lo < hi: mi = (lo + hi) / 2 if possible(mi): hi = mi else: lo = mi + 1 return lo
[sol1]
class Solution { public int smallestDistancePair(int[] nums, int k) { Arrays.sort(nums); int WIDTH = 2 * nums[nums.length - 1]; //multiplicity[i] = number of nums[j] == nums[i] (j < i) int[] multiplicity = new int[nums.length]; for (int i = 1; i < nums.length; ++i) { if (nums[i] == nums[i-1]) { multiplicity[i] = 1 + multiplicity[i - 1]; } } //prefix[v] = number of values <= v int[] prefix = new int[WIDTH]; int left = 0; for (int i = 0; i < WIDTH; ++i) { while (left < nums.length && nums[left] == i) left++; prefix[i] = left; } int lo = 0; int hi = nums[nums.length - 1] - nums[0]; while (lo < hi) { int mi = (lo + hi) / 2; int count = 0; for (int i = 0; i < nums.length; ++i) { count += prefix[nums[i] + mi] - prefix[nums[i]] + multiplicity[i]; } //count = number of pairs with distance <= mi if (count >= k) hi = mi; else lo = mi + 1; } return lo; } }

复杂度分析

  • 时间复杂度:$O(W + N \log W + N \log N)$,其中 $N$ 为 nums 数组的长度,$W$ 为 nums 数组中最大值与最小值的差,即 nums[nums.length - 1] - nums[0](对 nums 数组进行排序之后)。其中计算 prefix 的时间复杂度为 $O(W)$,二分查找的时间复杂度为 $\log W$,计算 possible(guess) 函数的时间复杂度为 $O(N)$,对 nums 数组进行排序的时间复杂度为 $O(N\log N)$。

  • 空间复杂度:$O(N + W)$,用来存储数组 multiplicityprefix

方法三:二分查找 + 双指针 [通过]

分析

在方法二中,我们计算 possible(guess) 时用到了很多预先处理好的数组,我们可以优化这个过程,减少预处理的时间复杂度,例如计算 prefix 的时间复杂度 $O(W)$。

方法

我们可以使用双指针来计算出所有小于等于 guess 的距离对数目。我们维护 leftright,其中 right 通过循环逐渐递增,left 在每次循环中被维护,使得它满足 nums[right] - nums[left] <= guess 且最小。这样对于 nums[right],以它为右端的满足距离小于等于 guess 的距离对数目即为 right - left。我们在循环中对这些 right - left 进行累加,就得到了所有小于等于 guess 的距离对数目。

[sol3]
class Solution(object): def smallestDistancePair(self, nums, k): def possible(guess): #Is there k or more pairs with distance <= guess? count = left = 0 for right, x in enumerate(nums): while x - nums[left] > guess: left += 1 count += right - left return count >= k nums.sort() lo = 0 hi = nums[-1] - nums[0] while lo < hi: mi = (lo + hi) / 2 if possible(mi): hi = mi else: lo = mi + 1 return lo
[sol3]
class Solution { public int smallestDistancePair(int[] nums, int k) { Arrays.sort(nums); int lo = 0; int hi = nums[nums.length - 1] - nums[0]; while (lo < hi) { int mi = (lo + hi) / 2; int count = 0, left = 0; for (int right = 0; right < nums.length; ++right) { while (nums[right] - nums[left] > mi) left++; count += right - left; } //count = number of pairs with distance <= mi if (count >= k) hi = mi; else lo = mi + 1; } return lo; } }

复杂度分析

  • 时间复杂度:$O(N \log W + N \log N)$,其中 $N$ 为 nums 数组的长度,$W$ 为 nums 数组中最大值与最小值的差,即 nums[nums.length - 1] - nums[0](对 nums 数组进行排序之后)。其中二分查找的时间复杂度为 $\log W$,计算 possible(guess) 函数的时间复杂度为 $O(N)$,对 nums 数组进行排序的时间复杂度为 $O(N\log N)$。

  • 空间复杂度:$O(1)$。

统计信息

通过次数 提交次数 AC比率
9640 25622 37.6%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
查找和最小的K对数字 中等
有序矩阵中第 K 小的元素 中等
找到 K 个最接近的元素 中等
乘法表中第k小的数 困难
第 K 个最小的素数分数 困难
上一篇:
718-最长重复子数组(Maximum Length of Repeated Subarray)
下一篇:
720-词典中最长的单词(Longest Word in Dictionary)
本文目录
本文目录