前幾天，阮一峰 和 winter 在前端九部組織了一個互面小組，目的是為了分享和解答面試遇到的面試題，感興趣的可以了解一下。

下面我就把我回答的一個問題整理出來分享給大家。

問題描述

題目是：算法，前 K 個最大的元素。

這個題目非常簡短，第一眼看上去可能不知道是什么意思。翻譯一下：

給定一個數字類型的數組和一個正整數 K，找出數組中前 K 個最大的元素。

這個題目網速也有很多的講解，我也是根據網上提供的一些思路來實現的，下面就是我根據其中三種方法的實現：

解答

解法一：

思路

最簡單的方法就是對數組進行排序，然后取前 K 位就可以了。

實現

/*** 查找前 K 個最大的元素* * @param {number[]} arr - 要查詢的數組* @param {number} k - 最大個數* * @return {number[]}*/
const findKMax = (arr, k) => {return arr.sort((a, b) => b - a).slice(0, k);
}
復制代碼

解法二

思路

解法一用了 js 的 sort 來實現排序，但是復雜度比較高，數據量大的話會比較慢。仔細分析一下題目，找出前 K 個最大的元素，但并沒有要求對其排序，所以不用對所有的數都進行排序。分治法就會快很多：

假設有 n 個數存在數組 S 中，從數組 S 中隨機找一個元素 X，遍歷數組，比 X 大的放在 S1 中，比 X 小的放在 S2 中，那么會出現以下三種情況：

S1 的數字個數等于 K，結束查找，返回 S1; S1 的數字個數大于 K，繼續在 S1 中找取最大的K個數字; S1 的數字個數小于 K，繼續在 S2 中找取最大的 K-S1.length 個數字，拼接在 S1 后; 這樣遞歸下去，就可以找出答案來了。下面看具體的實現：

實現

/*** 分割數組* * @typedef {Object} Partition* @property {number[]} Partition.maxarr* @property {number[]} Partition.minarr* * @param {number[]} arr - 要分割的數組* * @returns {Partition} res - 返回結果*/
const partition = (arr) => {const length = arr.length; // 數組長度const mid = ~~(length / 2); // 取數組中間的位置，可隨機const middle = arr[mid]; // 數組中間的值const maxarr = []; // 比中間值大const minarr = []; // 比中間值小// 數組長度為 2 的要特殊處理if (length === 2) {maxarr.push(Math.max(arr[0], arr[1]));minarr.push(Math.min(arr[0], arr[1]));} else {arr.forEach((v, i) => {if (i !== mid) {if (v >= middle) {maxarr.push(v);} else {minarr.push(v);}}})// 將中間值放到 maxarr 的最后一位maxarr.push(middle);}return { maxarr, minarr }
}/*** 查找前 K 個最大的元素* * @param {number[]} arr - 要查詢的數組* @param {number} k - 最大個數* * @return {number[]}*/
const findKMax = (arr, k) => {if (arr.length < k) {return arr;}// 分割數組const { maxarr, minarr } = partition(arr);if (maxarr.length === k) {return maxarr;}if (maxarr.length > k) {return findKMax(maxarr, k);}if (maxarr.length < k) {return maxarr.concat(findKMax(minarr, k - maxarr.length));}
}
復制代碼

解法三

思路

可以取數組的前 K 位構建一個小頂堆（也叫最小堆），這么堆頂就是前 K 位最小的值，然后從 K+1 遍歷數組，如果小于堆頂，則將其交換，并重新構建堆，使堆頂最小，這么遍歷結束后，堆就是最大的 K 位，堆頂是前 K 位的最小值。

實現

/*** 小頂堆葉子節點排序* @param {number[]} arr - 堆* @param {number} i = 父節點* @param {length} i - 堆大小*/
const heapify = (arr, i, length) => {const left = 2 * i + 1; // 左孩子節點const right = 2 * i + 2; // 右孩子節點let minimum = i; // 假設最小的節點為父結點// 確定三個節點的最小節點if (left < length && arr[left] < arr[minimum]) {minimum = left;}if (right < length && arr[right] < arr[minimum]) {minimum = right;}// 如果父節點不是最小節點if (minimum !== i) {// 最小節點和父節點交換const tmp = arr[minimum];arr[minimum] = arr[i];arr[i] = tmp;// 對調整的結點做同樣的交換heapify(arr, minimum, length);}}/*** 構建小頂堆* 從 n/2 個節點開始，依次構建堆，直到第一個節點* * @param {number[]} arr */
const buildMinHeap = (arr) => {for (let i = Math.floor(arr.length / 2); i >= 0; i--) {heapify(arr, i, arr.length)}return arr;
}/**·* 查找前 K 個最大的元素* * @param {number[]} arr - 要查詢的數組* @param {number} k - 最大個數* * @return {number[]}*/
const findKMax = (arr, k) => {// 取數組的前 K 位構建小頂堆const newArr = [...arr];const kMax = arr.slice(0, k)buildMinHeap(kMax);// 堆后面的進行遍歷，如果比堆頂大，則交換并重新構建堆for (let i = k; i < newArr.length; i++) {if (newArr[i] > kMax[0]) {const tmp = kMax[0];kMax[0] = newArr[i];newArr[i] = tmp;buildMinHeap(kMax);}}return kMax;
}
復制代碼

總結

上面就是我對這個題目的三種解法，其實還有幾種解法，因為精力原因沒有探究，大家可以自己去網上了解一下。

上述解法如果有問題還請指正。