前几天，阮一峰 和 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;}复制代码 总结
上面就是我对这个题目的三种解法，其实还有几种解法，因为精力原因没有探究，大家可以自己去网上了解一下。
上述解法如果有问题还请指正。