leetcode
leetcode 601 ~ 650
找出第 K 小的数对距离

找出第 K 小的数对距离

难度:

标签:

题目描述

代码结果

运行时间: 50 ms, 内存: 16.7 MB

/*
 * 思路：
 * 1. 首先对数组进行排序。
 * 2. 使用Stream生成所有可能的数对距离。
 * 3. 对这些距离进行排序，然后获取第k小的距离。
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class KthSmallestPairDistanceStream {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        return IntStream.range(0, nums.length)
                .boxed()
                .flatMap(i -> IntStream.range(i + 1, nums.length)
                        .map(j -> Math.abs(nums[j] - nums[i]))
                        .boxed())
                .sorted()
                .skip(k - 1)
                .findFirst()
                .orElse(-1);
    }
}

解释

方法:

这个题解使用了二分查找的思路。首先将数组 nums 排序，然后二分枚举可能的距离值 mid，统计所有距离小于等于 mid 的数对数量 cnt。如果 cnt >= k，说明第 k 小的距离一定不超过 mid，我们可以缩小上界；否则我们需要增大下界。最后二分出第 k 小的距离。

时间复杂度:

O(nlog(n+D))

空间复杂度:

O(logn)

代码细节讲解

🦆
在解题思路中，你是如何决定使用二分查找方法来解决这个问题的？
▷
考虑到数对距离的值域是有序的（最小的距离是0，最大的距离是数组中最大值与最小值之差），并且当我们知道有k个数对的距离小于等于某个值时，可以推断出第k小的数对距离不会超过这个值。这个性质使得我们可以使用二分查找在有序的值域内快速逼近第k小的距离，因为我们可以通过统计操作来验证每一个'猜测'是否合理，从而高效地缩小搜索范围。
🦆
函数`count(mid: int)`的逻辑是如何确保统计的是所有小于等于`mid`的数对数量？
▷
函数`count(mid: int)`通过遍历排序后的数组，并使用双指针技术统计每个元素作为数对较大数时，与之前元素的差不超过`mid`的数量。具体实现中，外层循环固定较大数`num`，内层循环的指针`i`移动直到`num - nums[i]`大于`mid`为止，此时`[i, j)`的所有数与`num`的差都不超过`mid`，通过`j - i`计算这些数对的数量，累加得到总的符合条件的数对数量。
🦆
在二分查找中，为什么选择`nums[-1] - nums[0]`作为二分查找的上界，而不是数组中的其他可能的数值范围？
▷
在排序后的数组中，`nums[-1] - nums[0]`即是数组中最大值与最小值的差，代表了可能的最大数对距离。由于数对距离的定义（任意两数的绝对差值），任何两数的差值都不会超过这个最大差值。因此，使用`nums[-1] - nums[0]`作为上界是合理的，它确保了覆盖所有可能的数对距离，避免遗漏，同时也没有不必要地扩大搜索范围。
🦆
在统计函数中，`while`循环的条件`num - nums[i] > mid`是如何帮助优化性能的？
▷
该`while`循环通过移动指针`i`来排除那些与`num`的差值超过`mid`的数对。这样，每次外层循环迭代到新的`num`时，内层循环不需要从头开始计算，而是从上一次的`i`位置继续，避免了重复的比较和计算。这种方法称为双指针或滑动窗口技术，大大提升了函数的效率，使其能在较大的数据集上运行得更快。

相关问题

查找和最小的 K 对数字

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。

 

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

 

提示:

  • 1 <= nums1.length, nums2.length <= 105
  • -109 <= nums1[i], nums2[i] <= 109
  • nums1 和 nums2 均为 升序排列
  • 1 <= k <= 104
  • k <= nums1.length * nums2.length

有序矩阵中第 K 小的元素

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

 

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：

输入：matrix = [[-5]], k = 1
输出：-5

 

提示：

  • n == matrix.length
  • n == matrix[i].length
  • 1 <= n <= 300
  • -109 <= matrix[i][j] <= 109
  • 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
  • 1 <= k <= n2

 

进阶：

  • 你能否用一个恒定的内存(即 O(1) 内存复杂度)来解决这个问题?
  • 你能在 O(n) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。

找到 K 个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

  • |a - x| < |b - x| 或者
  • |a - x| == |b - x| 且 a < b

 

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：

输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]

 

提示：

  • 1 <= k <= arr.length
  • 1 <= arr.length <= 104
  • arr 按 升序 排列
  • -104 <= arr[i], x <= 104

乘法表中第k小的数

几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第 k 小的数字吗？

乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j（下标从 1 开始）。

给你三个整数 m、n 和 k，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字。

 

示例 1：

输入：m = 3, n = 3, k = 5
输出：3
解释：第 5 小的数字是 3 。

示例 2：

输入：m = 2, n = 3, k = 6
输出：6
解释：第 6 小的数字是 6 。

 

提示：

  • 1 <= m, n <= 3 * 104
  • 1 <= k <= m * n

第 K 个最小的质数分数

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 质数 组成，且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。

那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。

 

示例 1：

输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

示例 2：

输入：arr = [1,7], k = 1
输出：[1,7]

 

提示：

  • 2 <= arr.length <= 1000
  • 1 <= arr[i] <= 3 * 104
  • arr[0] == 1
  • arr[i] 是一个 质数 ，i > 0
  • arr 中的所有数字 互不相同 ，且按 严格递增 排序
  • 1 <= k <= arr.length * (arr.length - 1) / 2

 

进阶：你可以设计并实现时间复杂度小于 O(n2) 的算法解决此问题吗？

最长重复子数组词典中最长的单词