面试题30:最小的K个数

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

思路一:如果允许修改数组,可采用Partition

思路二:我们可以先创建一个大小为k的数据容器来存储最小的k个数字,接下来我们每次从输入的n个整数中读如一个数。如果容器中的数字少于k个,则直接把数字加入容器中;如果容器中已有k个数字了,找出已有的k个数中最大值,然后插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值小,则用这个数替代当前已有的最大值;如果待插入的值比当前已有的最大值还要大,抛弃这个整数。


©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 题目:输入n个整数,找出其中最小的k个数。 解法:top K问题。如果n不大,可以一次性载入内存,则用一个数组保存...
    qmss阅读 316评论 0 0
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 34,735评论 18 399
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题 本文经过大量细致的优化后,收录于我的新书《编程之法》第六章中,新书...
    Helen_Cat阅读 7,587评论 1 39
  • 1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不...
    曲终人散Li阅读 3,505评论 0 19
  • 从三月份找实习到现在,面了一些公司,挂了不少,但最终还是拿到小米、百度、阿里、京东、新浪、CVTE、乐视家的研发岗...
    时芥蓝阅读 42,818评论 11 349

友情链接更多精彩内容