创建博客 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TOTO

Think and Be Different

 
 
 

日志

 
 
关于我

宠辱不惊,闲看庭前花开花落.去留无意,静随天边云卷云舒。

LOFTER精选

第K小数的两个算法  

2007-04-29 10:36:32|  分类: 默认分类 |  标签: |举报 |字号 订阅

以前写的,昨天才发现,前一个算法的复杂度是O(n)的,呵呵

在一个数组中,找出第K小的数。

这是我在以前别人的BLOG里面看到的一个题目,几乎所有的人都用快速排序的思想来做的。

还是找个中间点,如果中间点的位置为K,那么它就是那个元素,否则如果>K,就在左边继续用PARTITION的算法,如果< p />

这个和PAR方法的思想一致。

下面是我今天上自习的时候想到的一种方法。

我用下面的思想来做这个问题:

首先我们先对数组的前K个数进行堆排序【K个数的最大堆】,然后对剩下的N-K的数字,依次加入堆,并将最大值退出堆。

最后的堆顶元素就是第K小的数字。

代码就不写了,分析一下复杂度,O(n)建堆log(k),然后的插入堆的比较次数最多是(n-k)log(k),

所以它的复杂度比较平均,在极端情况下它的效率也是很高的。

这里有个人写的代码,用上面第一种方法得到的

http://bbs.chinaunix.net/viewthread.php?tid=116218

  评论这张
 
阅读(1038)| 评论(0)
推荐 转载

历史上的今天

最近读者

热度

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2014