文档章节

找出N个整数中最大的K个数

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 502
阅读 15
收藏 0

问题:在N个数据中查找到第k个大的值。

原文地址


所谓“第(前)k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第(前)k个数的问题。

解法1:我们可以对这个乱序数组按照从大到小先行排序,然后取出前k大,总的时间复杂度为O(n*logn + k)。
 
解法2:利用选择排序或交互排序,K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)
 
解法3:利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有两种情况:
           1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;
           2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n)
 
解法4:二分[Smin,Smax]查找结果X,统计X在数组中出现,且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)
 
解法5:用O(4*n)的方法对原数组建最大堆,然后pop出k次即可。时间复杂度为O(4*n + k*logn)
 
解法6:维护一个k大小的最小堆,对于数组中的每一个元素判断与堆顶的大小,若堆顶较大,则不管,否则,弹出堆顶,将当前值插入到堆中。时间复杂度O(n * logk)
 
解法7:利用hash保存数组中元素Si出现的次数,利用计数排序的思想,线性从大到小扫描过程中,前面有k-1个数则为第k大数,平均情况下时间复杂度O(n)

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/03/26/5637107.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
10亿个数中找出最大的10000个数(top K问题)

这个问题还是建立最小堆比较好一些。 先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,...

一贱书生
2016/11/28
244
0
寻找最大的K个数,Top K问题的堆实现

前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。 先拿100...

天天顺利
05/18
0
0
百度2017春招笔试真题编程题集合

百度2017春招笔试真题编程题集合 买帽子 数据结构 度度熊想去商场买一顶帽子,商场里有N顶帽子,有些帽子的价格可能相同。度度熊想买一顶价格第三便宜的帽子,问第三便宜的帽子价格是多少? ...

TinyDolphin
02/24
0
0
海量数据面试题整理1.给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是

海量数据面试题整理   1. 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?   方案1:可以估计每个文件安的大小为50G×64=320G,远远...

今幕明
2015/01/30
0
0
大数据处理面试题

给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 方an1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G。所以不可能将...

zyt_1978
2016/04/14
130
0

没有更多内容

加载失败,请刷新页面

加载更多

关于网站恶意注册会员

网站发生恶意注册会员,有图形验证码 ,和短信验证码 但是还是有大量恶意注册: session 和 cookie都是可以随便伪造的。 验证码有打码平台。 短信验证有短信验证平台。 IP限制有虚拟拨号/VP...

妖尾巴
28分钟前
0
0
awk命令用法介绍

10月18日任务 9.6/9.7 awk 9.6/9.7 awk命令 head -n2 test.txt|awk -F ':' '{print $1}' head -n2 test.txt|awk -F ':' '{print $0}' awk -F ':' '{print $1"#"$2"#"$3"#"$4}' awk '/oo/ tes......

zgxlinux
29分钟前
0
0
循环

我今天学会了用for循环找出一个数组中的最大值,代码: var rets = [2,4,5,6,7,9,10,15];function arrayMax(arrs) {var max = arrs[0];for(var i = 1,ilen = arrs.length; i < ilen...

墨冥
34分钟前
0
0
10《Java核心技术》之如何保证集合是线程安全的? ConcurrentHashMap如何实现高效地线程安全?

一、提出问题 之前我们一起讨论过两讲 Java 集合框架的典型容器类,它们绝大部分都不是线程安全的,仅有的线程安全实现,比如 Vector、Stack,在性能方面也远不尽如人意。幸好 Java 语言提供...

飞鱼说编程
38分钟前
2
0
SpringBoot 整合 kafka 实现组订阅模式

SpringBoot 整合 kafka 实现组订阅模式: 工程结构图 消息生产者pom.xml配置 <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xml......

泉天下
43分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部