文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 502
阅读 18
收藏 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
大数据处理面试题

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

zyt_1978
2016/04/14
130
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
百度2017春招笔试真题编程题集合

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

TinyDolphin
02/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CSS实例详解:Flex布局

本文由云+社区发表 本文将通过三个简单的实例,实际应用上篇文章的基础理论知识,展示下Flex布局是如何解决CSS布局问题。 一.垂直居中 这里同时用非flex布局和flex布局两种方式来实现,可以...

腾讯云加社区
3分钟前
0
0
安装全局webpack

https://www.jianshu.com/p/119a825d8bba npm ls webpack 和npm ls webpack -g 查看本地和全局版本 npm install webpack@1.15.0 -g 全局 然后到项目里面 npm install npm init npm install w......

lsy999
15分钟前
0
0
/etc/profile和/etc/environment的区别

/etc/profile 文件 当一个用户登录Linux系统或使用 su 命令切换到另一个用户时,设置用户环境第一个读取的文件就是 /etc/profile ,此文件为系统全局变量配置文件,且仅仅在第一次登录系统时...

calmsnow
21分钟前
2
0
rabbitMQ日常管理(转)

一、网页登录方法 http://127.0.0.1:15672/ 用户名和密码默认为guest/guest 用java代码去连接rabbitmq用的端口是5672 二、rabbitMQ基本概念 RabbitMQ是一个开源的AMQP实现,服务器端用Erlan...

__HuWei
27分钟前
1
0
gitlab cicd

https://docs.gitlab.com/ee/ci/docker/using_docker_build.html

kut
27分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部