找出陣列中第 k 大的數字及其出現次數

摘要： 這是前端面試過程中遇到的一道演算法題，雖說難度不大，但是也有些細節的地方需要仔細考慮。 比如說陣列 [1, 2, 4, 4, 3, 5]，第 2 大的數字是 4，出現了 2 次。下面以這個為例展開演算法的講解。 先說說大體的思路，然後再考慮一些細節性的問題。 ...

這是前端面試過程中遇到的一道演算法題，雖說難度不大，但是也有些細節的地方需要仔細考慮。

比如說陣列 [1, 2, 4, 4, 3, 5]，第 2 大的數字是 4，出現了 2 次。下面以這個為例展開演算法的講解。

先說說大體的思路，然後再考慮一些細節性的問題。

• 既然涉及到數字大小的問題，那就要對給定陣列進行排序，題目要求“第 k 大”的數字，故選擇降序的方式更有利於後面的查詢；

• 重點來了，需要遍歷陣列，對當前遍歷到的陣列元素的大小排名和 k 值進行比較，若排名大於 k 值則結束迴圈；如果排名等於 k 值，則將該陣列元素記為第 k 大的數字，且次數加一；

• 那如何確定遍歷的當前陣列元素的大小排名呢？我們先將陣列的第一項定為第 1 大的數字，然後比較第一項和第二項是否相等，若相等則第二項也為第 1 大；如果不相等則陣列第二項為第 2 大的數字。依次類推，可獲知每次遍歷的陣列元素的大小排名。

整體的思路講完了，現在看看細節性的東西——邊界判斷

• 給定的 k 值是否大於或等於 1（保證沒有第 0 大的數字），且 k 值小於或等於陣列的長度（因為陣列經降序排序後，值最小的陣列元素的大小排名值不可能比陣列長度值更大）。這條判斷隱含了陣列不能為空的條件。

• 遍歷結束時，k 值不能超出值最小的陣列元素的大小排名，若超出了，說明陣列中不存在這樣的數字。

根據以上思路和細節考慮寫出的演算法如下：

function findKthNum (arr, k) {
var len = arr.length;
// 對給定的 k 值進行判斷，確保 len >= k >= 1
if (k > len || k < 1) {
console.log("There doesn't exists the number you want !");
return;
}
// 獲得陣列的副本
var _arr = arr.slice();
// 遍歷陣列時，當前陣列元素的大小排名
var rank = 1;
// 第 k 大的數字
var num = 0;
// 第 k 大數字的出現次數
var count = 0;
// 對 _arr 進行降序排序
_arr.sort(function (a, b) {
return b - a;
});
for (var i = 0; i < len; i++) {
var j = i + 1;
// 對當前陣列元素的大小排名和 k 值進行比較，若排名大
// 於 k 值則結束迴圈；如果排名等於 k 值，則將該陣列
// 元素記為第 k 大的數字，且次數加一。
if (rank > k) {
break;
} else if (rank == k) {
num = _arr[i];
count++;
}
// 若當前遍歷的陣列項與下一項數字不相等，則說明下一個
// 數字的排名值比當前遍歷數字的排名剛好大 1
if ((j < len) && (_arr[i] != _arr[j])) {
rank++;
}
}
// 遍歷結束時，若最後遍歷的陣列元素的大小排名小於給定的 k 值，則說
// 明陣列中沒有第 k 大的數字，即 k 值超出了所有陣列元素的大小排名。
if (rank < k) {
console.log("There doesn't exists the number you want !");
} else {
console.log('第' + k + '大的數字：' + num, '出現次數：' + count);
}
}
複製程式碼

最後給出一些測試用例：

// 正常情況，findKthNum(arr1, 2)
var arr1 = [1, 2, 4, 4, 3, 5];

// 陣列為空，findKthNum(arr2, 2)
var arr2 = [];

// k 值小於 1，findKthNum(arr3, 0)
var arr3 = [1, 2, 4, 4, 3, 5];

// k 值大於陣列長度，findKthNum(arr4, 7)
var arr4 = [1, 2, 4, 4, 3, 5];

// k 值超出了所有陣列元素的大小排名，findKthNum(arr5, 6)
var arr5 = [1, 2, 4, 4, 3, 5];
複製程式碼