資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告