JavaScript 最小的 K 个数

🌙
手机阅读
本文目录结构

最小的 K 个数

题目:

输入 n 个整数,找出其中最小的 K 个数。例如输入 4,5,1,6,2,7,3,8 这8个数字,则最小的4个数字是 1,2,3,4 。

思路:

(1)第一种思路是首先将数组排序,排序后再取最小的 k 个数。这一种方法的时间复杂度取决于我们选择的排序算法的时间复杂 度,最好的情况下为 O(nlogn)。

(2)第二种思路是由于我们只需要获得最小的 k 个数,这 k 个数不一定是按序排序的。因此我们可以使用快速排序中的 part ition函数来实现。每一次选择一个枢纽值,将数组分为比枢纽值大和比枢纽值小的两个部分,判断枢纽值的位置,如果该枢 纽值的位置为 k-1 的话,那么枢纽值和它前面的所有数字就是最小的 k 个数。如果枢纽值的位置小于 k-1 的话,假设枢 纽值的位置为 n-1,那么我们已经找到了前 n 小的数字了,我们就还需要到后半部分去寻找后半部分 k-n 小的值,进行划 分。当该枢纽值的位置比 k-1大时,说明最小的 k 个值还在左半部分,我们需要继续对左半部分进行划分。这一种方法的平 均时间复杂度为 O(n)。

(3)第三种方法是维护一个容量为 k 的最大堆。对数组进行遍历时,如果堆的容量还没有达到 k ,则直接将元素加入到堆中,这 就相当于我们假设前 k 个数就是最小的 k 个数。对 k 以后的元素遍历时,我们将该元素与堆的最大值进行比较,如果比最 大值小,那么我们则将最大值与其交换,然后调整堆。如果大于等于堆的最大值,则继续向后遍历,直到数组遍历完成。这一 种方法的平均时间复杂度为 O(nlogk)。

详细资料可以参考: 《寻找最小的 k 个数》

更多面试题

如果你想了解更多的前端面试题,可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题,也有一些大公司的面试图,可以让你面试更加顺利。

面试题
HTML CSS JavaScript
jQuery Vue.js React
算法 HTTP Babel
BootStrap Electron Gulp
Node.js 前端经验相关 前端综合
Webpack 微信小程序 -

这些题库还在更新中,如果你有不错的面试题库欢迎分享给我,我整理后放上来;人人为我,我为人人,互帮互助,共同提高,祝大家都拿到心仪的Offer!

AXIHE / 精选资源

浏览全部教程

面试题

学习网站

前端培训
自己甄别

前端书籍

关于朱安邦

我叫 朱安邦,阿西河的站长,在杭州。

以前是一名平面设计师,后来开始接接触前端开发,主要研究前端技术中的JS方向。

业余时间我喜欢分享和交流自己的技术,欢迎大家关注我的 Bilibili

关注我: Github / 知乎

于2021年离开前端领域,目前重心放在研究区块链上面了

我叫朱安邦,阿西河的站长

目前在杭州从事区块链周边的开发工作,机械专业,以前从事平面设计工作。

2014年底脱产在老家自学6个月的前端技术,自学期间几乎从未出过家门,最终找到了满意的前端工作。更多>

于2021年离开前端领域,目前从事区块链方面工作了