文档章节

IT公司100题-5-查找最小的k个元素

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/11/02 12:08
字数 472
阅读 111
收藏 4

问题描述:

输入n 个整数,输出其中最小的k 个。

例如输入8, 7, 6, 5, 4, 3, 2, 1这8 个数字,则最小的3 个数字为3, 2, 1。


问题分析:

时间复杂度O(nlogn)方法:

对n个整数升序排序,取数组前面k个数就是最小的k个数,时间复杂度为O(nlogn),空间复杂度为O(1)。

大顶堆,时间复杂度为O(nlogk):

我们可以采用大顶堆来保存最小的k个数,堆顶元素就是k个最小的数中最大的。新来一个元素的时候,与堆顶元素进行比较,如果比堆顶元素大,则直接丢弃。如果比堆顶元素小,则替换堆顶元素,并且进行大顶推的调整,需要O(logk)的时间。所以总的时间复杂度为O(nlogk),空间复杂度为O(k)。

TreeSet时间复杂度为O(nlogk):

TreeSet容器的内部结构通常由红黑树来实现,所以查找、删除和插入操作都只需要O(logk)的时间。


代码实现:

package oschina.IT100;
/**
 * @project: oschina
 * @filename: IT5.java
 * @version: 0.10
 * @author: JM Han
 * @date: 10:52 2015/11/2
 * @comment: 输入n 个整数,输出其中最小的k 个。
 * @comment: 例如输入8, 7, 6, 5, 4, 3, 2, 1这8 个数字,则最小的3 个数字为3, 2, 1。
 * @result:
 */

import java.util.*;
import static tool.util.*;

public class IT5 {
   public static final int NUM = 3;
   public static void find3least(List<Integer> lst){
      TreeSet<Integer> innerlst = new TreeSet<Integer>();
      for (int i = 0; i < lst.size(); i++) {
         int x = lst.get(i);
         if(innerlst.size() < NUM) {
            innerlst.add(x);
         } else {
            int max = innerlst.last();
            if(x < max){
               innerlst.add(x);
               innerlst.remove(max);
            }
         }
      }
      if(innerlst.size() != 0){
         printGenericIterator(innerlst.iterator());
      }
   }

   public static void main(String[] args) {
      Integer[] testArray = new Integer[]{8, 7, 6, 5, 4, 3, 2, 1};
      List<Integer> lst = Arrays.asList(testArray);
      Integer[] arra = lst.toArray(new Integer[0]);
      for(Integer i:arra)
         System.out.print(i+" ");
      System.out.println();
      find3least(lst);
   }
}

代码输出:

8 7 6 5 4 3 2 1 
1 2 3


© 著作权归作者所有

关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
查找和排序:旋转数组的最小数字

题目描述 最近事情比较少,空闲比较多,就刷刷剑指Offer上的经典题。把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组...

lingfeng95
07/08
0
0
LeetCode.1005-K次取负数组和最大(Maximize Sum Of Array After K Negations)

这是悦乐书的第376次更新,第403篇原创 01 看题和准备 今天介绍的是算法题中级别的第题(顺位题号是)。给定一个整数数组,我们必须按以下方式修改数组:我们选择一个i并用替换,重复这个过程...

小川94
07/07
0
0
在海量数据里查询多少条数据的这类问题经常被问起,该如何回答?

1、海量日志数据,提取出某日访问百度次数最多的那个IP IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。 再详细介绍下此方案:首先是这一天,并且是...

瑞查德-Jack
01/08
81
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
🔥 面试必备:高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集 🔥

本文将覆盖 + + + 方面的面试算法题,文中我将给出: 面试中的题目 解题的思路 特定问题的技巧和注意事项 考察的知识点及其概念 详细的代码和解析 在开始之前,我们先看下会有哪些重点内容:...

_yuanhao
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

启动参数

常用启动参数,通过 -Dxx.yy=zz注入应用参数 -Deureka.instance.metadata-map.starkGroup=test3 -Dserver.port=8989 本地调试过程中,可改变端口来启动多个相同服务。修改启动的VM参数即可...

ZH-JSON
今天
6
0
ES配置修改

查看配置 GET /_cluster/settings 修改配置 PUT /_cluster/settings{ "persistent" : { "xpack" : { "monitoring" : { "collection" : { "enabled" : ......

messud4312
今天
4
0
Spring事务传播属性有那么难吗?看这一篇就够了

Spring事务传播属性有那么难吗?看这一篇就够了 笔者文笔功力尚浅,如有不妥,请慷慨指出,必定感激不尽 学习东西要知行合一,如果只是知道理论而没实践过,那么掌握的也不会特别扎实,估计过...

不学无数的程序员
今天
7
0
VMware vSphere ESXi主机的访问控制

在vShpere中,访问ESXi主机的途径很多,如下: ESXi DCUI ESXi Shell ESXi SSH ESXi Host Client vCenter --> vSphere web client / vSphere Client VMware vSphere ESXi主机的访问控制,除了......

大别阿郎
今天
6
0
大神讲解CGI、FastCGI和PHP-FPM关系图解

参考资料 概念了解:CGI,FastCGI,PHP-CGI与PHP-FPM:http://www.nowamagic.net/librarys/veda/detail/1319 php中fastcgi和php-fpm是什么东西:https://www.zybuluo.com/phper/note/50231 ......

网络小虾米
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部