企业宣传网站建设需求说明书的模板,建设学校网站的作用,雅联网站建设,wordpress不适合大型网站前几天#xff0c;阮一峰 和 winter 在前端九部组织了一个互面小组#xff0c;目的是为了分享和解答面试遇到的面试题#xff0c;感兴趣的可以了解一下。 下面我就把我回答的一个问题整理出来分享给大家。 问题描述 题目是#xff1a;算法#xff0c;前 K 个最大的元素。 …前几天阮一峰 和 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 位最小的值然后从 K1 遍历数组如果小于堆顶则将其交换并重新构建堆使堆顶最小这么遍历结束后堆就是最大的 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;
}
复制代码总结 上面就是我对这个题目的三种解法其实还有几种解法因为精力原因没有探究大家可以自己去网上了解一下。 上述解法如果有问题还请指正。
