博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
输入一个数组,求最小的K个数
阅读量:5341 次
发布时间:2019-06-15

本文共 441 字,大约阅读时间需要 1 分钟。

被这道题困了好久,看了剑指Offer才知道OJ上的要求有点迷惑性。

题目:

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

 

一直以为要按照顺序输出,想的方法是插入排序算法复杂度是O(N*K),当然这个地方就显得自己有点蠢了。不过我想在“按序输出”的错误题意下还没有啥更好的方法。

然后看了剑指Offer原书,原来输出不必按照顺序。所以第一种方法是快速选择。这种方法算法复杂度是O(N)。不过在实际的使用中可能有点隐含的时间参数。

第二种方法是维护一个大小为K的最大堆(或者红黑树,二叉树)。这个数据结构里面放了最小的K个数,每次把新加入的数字和其中最大的比较,如果小于最大的就插入,否则跳过。算法复杂度O(N*logK)。不过这个地方维护一个这样的数据结构其实还是有点困难的。面试的时候自己写代码不太容易。

转载于:https://www.cnblogs.com/dsj2016/p/5618046.html

你可能感兴趣的文章
更改MySQL数据库的编码为utf8mb4
查看>>
web应用
查看>>
关于报错”已有打开的于此Command相关联的DataReader,必须首先将它关闭。“的问题...
查看>>
Ubuntu--smb配置文件详解
查看>>
本学期软件工程课的感受
查看>>
C# http请求
查看>>
神秘的程序员(娱乐)
查看>>
水平和垂直居中
查看>>
第二周博客作业
查看>>
Python标准库笔记(6) — struct模块
查看>>
纠结的小键盘
查看>>
swift 2.0 语法 可选类型
查看>>
浅谈javascript中的call、apply、bind
查看>>
C++primer梗概——第3章
查看>>
Linux基本命令
查看>>
基于.NET平台常用的框架整理
查看>>
C#正则表达式快速入门提升教程
查看>>
beautifulsoup的简单使用
查看>>
面向对象--反射
查看>>
浏览器百度点击第二页时仍然跳转到第一页
查看>>