找出m个数中最小的n个数的算法

这个问题属于常见问题了,我的办法是采用堆。

截取STL中的partial_sort算法的实现:

template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
  RandomAccessIterator last, T*, Compare comp) {
  make_heap(first, middle, comp);
  for (RandomAccessIterator i = middle; i < last; ++i)
    if (comp(*i, *first))
      __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
  sort_heap(first, middle, comp);
}

上面这个函数是对一个序列进行部分排序,排序之后,在first,middle之间的元素有序。

它的做法首先将原始的first,middle中的数据生成一个堆,然后遍历之后的数据,如果比前面的元素中最大的元素大,就把最小的元素删除插入这个新的元素,这个过程是lg(middle - first),最后进行堆排序。

不是每个元素都需要重新调整堆,所以最坏的情况时间复杂度是n * lg(middle - first)。

类似的,可以根据这个算法并且使用堆算法解决这个问题,如上所言,最坏的时间复杂度是n * lg(m),其中n是元素总量,m是待查找的最大的m个数。

根据我上面的这个想法, 还有我原来写过的堆算法,给出解决这个问题的代码,由于我原来写的堆算法是大项堆(max-heap),也就是堆中最大的元素在根部,所以这里面求出来的是数中最小的10个数,如果要求最大的10个数,要讲这个堆改成小项堆,其实也就是改变堆中父子之间的大小关系罢了,其他的地方不变。

时间: 2024-08-31 04:34:59

找出m个数中最小的n个数的算法的相关文章

求解答-试编写一个算法,找出一个循环链表中的最小值。我是新手,编了一个程序,不知错在哪

问题描述 试编写一个算法,找出一个循环链表中的最小值.我是新手,编了一个程序,不知错在哪 #includeusing namespace std; class LinkNode{ int data; LinkNode *link; LinkNode(int d=0LinkNode *l=0){data=d;link=l;}}; class List{private: LinkNode *first; int n;public: List() { first=new LinkNode; first

找出两数组中不同的数据,并查看他们在以前数组中的索引值

问题描述 找出两数组中不同的数据,并查看他们在以前数组中的索引值 var aa = [1,21,21,21,28]; var bb = [3,4,27,39,21]; var cc = []; var tmp = aa.concat(bb); var o = {}; for (var i = 0; i < tmp.length; i ++){ (tmp[i] in o) ? o[tmp[i]] ++ : o[tmp[i]] = 1; } for (x in o){ if (o[x] == 1){

数组 算法-找出两数组中不同的数据,并查看他们在以前数组中的索引值

问题描述 找出两数组中不同的数据,并查看他们在以前数组中的索引值 var aa = [1,21,21,21,28]; var bb = [3,4,27,39,21]; var cc = []; var tmp = aa.concat(bb); var o = {}; for (var i = 0; i < tmp.length; i ++){ (tmp[i] in o) ? o[tmp[i]] ++ : o[tmp[i]] = 1; } for (x in o){ if (o[x] == 1){

找出给定字符串中出现最多的字符和次数

  "给定一个字符串,找出这个字符串中出现最多的字符和次数",笔试碰到的一个问题,还是比较简单的,贴出来与大家分享. public class CharCount { public static void Charcount(String string) { if (string == null) return; int[] count = new int[string.length()]; for (int i = 0; i < count.length; i++) { //

如何找出Linux系统中所有的*.cpp、*.h文件

如何找出Linux系统中所有的*.cpp.*.h文件? 用find命令就可以了.不过如果从根目录查找消耗资源较高,使用下面的命令就可以: find / -http://www.aliyun.com/zixun/aggregation/11696.html">name "*.cpp" -o -name "*.h" 示例: [root@localhost /]# find / -name "*.cpp" -o -name "

SQL语句练习实例之四 找出促销活动中销售额最高的职员_MsSql

复制代码 代码如下: ---找出促销活动中销售额最高的职员 ---你刚在一家服装销售公司中找到了一份工作,此时经理要求你根据数据库中的两张表得到促销活动销售额最高的销售员 ---1.一张是促销活动表 ---2.一张是销售客列表 create table Promotions ( activity nvarchar(30), sdate datetime, edate datetime ) insert Promotions select '五一促销活动','2011-5-1','2011-5-7

linux-Linux中怎么用grep找出一个文件中空白行的行数字=

问题描述 Linux中怎么用grep找出一个文件中空白行的行数字= 不知道为什么这样写# grep '^&' /etc/profile | wc -l找不出结果, 请问这个应该怎么写才是真确的? 解决方案 grep -E '^$' -n /etc/profile 解决方案二: 加上正则的参数,试试下面的命令 grep -e '^$' -n /etc/profile

List对象中存有整型数组,如何找出这些数组中对应位置上的最大值

问题描述 List对象中有几个长度相同的整型数组,如果再在List中循环找出这些数组中对应位置上的最大value,简单例子说明:假如有三个数组如下:int[]a1=newint[]{3,10,5,0};int[]a2=newint[]{1,9,7,6};int[]a3=newint[]{5,3,5,8};比较后得到新数组对象ax=newint[]{5,9,10,8};请问如何在遍历整个List情形下中实现呢?我的平台是VS2005,不能用LINQ实现.thanks 解决方案 解决方案二:你说你这

从M个数中任意选出N个数,罗列出所有的情况

问题描述 用 java 实现的简单思路是什么呢?? 问题补充:好像意思没表达清除,Input: int[m]output: int[n]下边 code 里边半天没能看出input,解答一下吧.谢谢阿programming 写道 解决方案 /** * @author Tony.Yan */public class Test { private int m; private int[] set; private boolean first; private int position; public