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!