数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学JavaScript中排序的二维数组的第N小元素
问题
假设我们有一个排序的数字数组（按升序排序），如下所示：
const arr = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ];
我们需要编写一个JavaScript函数，该函数将此类数组作为第一个参数，并将一个整数num作为第二个参数。
我们的函数应该返回数组arr中第num小的元素。
例如，如果函数的输入是：
const arr = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ]; const num = 5;
输出
则输出应为：
const output = 11;
输出解释
11是矩阵中第五小的元素。
示例
代码如下：
const arr = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
];
const num = 5;
const kthSmallest = (arr = [], num = 1) => {
let low = arr[0][0]
let high = arr[arr.length-1][arr[0].length-1] + 1;
while (low < high) {
let mid = low + Math.floor((high-low)/2);
let count = 0;
for (let i = 0;i<arr.length;i++) {
for (let j=0;j<arr.length;j++) {
if (arr[i][j] <= mid) count++;
else break;
}
}
if (count < num) low = mid+1;
else high = mid;
}
return low
};
console.log(kthSmallest(arr, num));代码解释
这里的思路是：
当我们有一个常规的排序二维数组时，我们使用一系列索引来查找目标，例如：
low = 0, high = length-1, mid = (low+high)/2
如果目标大于索引mid处的数字，则我们搜索右侧部分；如果目标小于，则我们搜索左侧。
但是，在这个二维排序数组中，不可能找到这样的中间索引。这里的思路是使用一系列数字来与我们的k进行测试。我们知道第一个数字是最小的，最后一个数字是最大的，这意味着我们的目标数字一定在两者之间。我们可以使用这两个数字作为我们的下界和上界，并将我们的中间值设置为两者之间的数字，并检查arr中小于该数字的数字有多少，并相应地调整下界和上界。
当我们恰好得到k个数字时，我们就知道我们找到了答案。这里极其棘手的一点是，仅仅通过查看我们如何计算中间值，很多时候我们正在测试的数字甚至可能不在arr中，因为最终，我们使用的数字只是任意数字。
为了解释这一点，我们需要想象我们的程序处于一个下界和上界几乎要碰撞的阶段。如果我们计数的数字少于预期，我们将设置low=mid+1，这可能会将我们的中间值增加1。通过将我们的中间值一次增加1，我们可以确保数字包含在arr中。
输出
控制台输出将是：
11
更新于：2021年3月18日
317 次浏览
广告