从n个数中取前m大的数有什么好的算法吗？

amw_demon 2007-10-11 09:54:59

从n个数中取前m大的数有什么好的算法吗？复杂度怎么样？

...全文

1027 20 打赏收藏转发到动态举报

写回复

用AI写文章

20 条回复

切换为时间正序

请发表友善的回复…

发表回复

zellux 2007-10-12

打赏
举报

oo:
的确是O(n)的，不过这个算法是在平均情况下O(n)
算法导论上还介绍了一种处理，可以在最差情况下达到O(n)的复杂度，不过这个方法不实用

zellux 2007-10-12

打赏
举报

算法导论上有最差情况下O(n)时间里求出第m大的数的算法，用的是paritition方法，得到这第m大的数以后，前面的m个数就是所求的了
（当然这m个数不是有序的）

medie2005 2007-10-12

打赏
举报

我要说的，mathe都说了，算法的复杂度确实是O(n)的。

Vitin 2007-10-12

打赏
举报

用长度m的数据结构记录前m个最大元素（可以是一个最小值堆）。
将前m个数建立成堆，复杂度是O(mlgm).对剩下的n-m个数，如果它大于堆中的最小值，则用新值代替原最小值，并重新调整成堆。对每个数，复杂度O(lgm).
因此，算法的整体复杂度是O(nlgm).在m远小于n时，复杂度趋近于O(n).

flushtime 2007-10-11

打赏
举报

这个可以利用堆排序的思想来做.
首先建立一个大顶堆,时间复杂度是O(n).
然后反复取堆顶元素并维持堆,每次维持堆的时间复杂度是O(lg n)
所以总的时间复杂度是O(n +m*lg n)

evifree 2007-10-11

打赏
举报

构造一个m个元素的堆Heap,
遍历这n个数，对每个数num,作以下操作:
1.若Heap未满，直接将num放入堆中,返回
2.将num与堆中最小元素比较，若num<=最小元素，返回
3.用num替换掉Heap中的最小元素，重新整理Heap

flushtime 2007-10-11

打赏
举报

楼上的时间复杂度是O(n)?
晕!

thecorr 2007-10-11

打赏
举报

构造一个链表首先存储前m个数并排序，对后面的每个数与链表中的数比较，大于某个数则删除掉最小的，按顺序插入此数，一直到遍历完毕，则链表里的值就是前m 大的数。复杂度 n

oo 2007-10-11

打赏
举报

1，类似于一棵二叉数，开始数据都在叶子上，两两比较，大的设置成他们的父亲，直到根，这个就是最大的，n-1次比较
2，然后取第二大的时，从最大元素从最底层上来的路线在冒一次，然后跟根的另一个儿子比较，大的就是第二大的，需要lgn次比较，
3，重复第二步知道m个数据取完
复杂度是n + mlgn

当然做的时候不一定要建一棵数，可以直接在数组里做，另外取掉的数可以用一个负无穷的哨兵替代。

arong1234 2007-10-11

打赏
举报

方法就是建立一个最大长度为m的链表，用插入排序方法向内挨个插元素

复杂度等于插入排序复杂度的n倍，如果n远大于m，如果不是远大于，复杂度比这个要小

我不记得插入排序的复杂度了，你去查查肯定能找到

mathe 2007-10-11

打赏
举报

取第m个数的确是O(n)的算法。算法同快速排序类似，只是这个时候，每一趟都只需要处理上一趟数据中的一部分

oo 2007-10-11

打赏
举报

medie2005:

你确定那个算法是O（n）吗？__unguarded_partition 里是否有遍历？

只知道取第m个数有nloglogn的算法

mathe 2007-10-11

打赏
举报

找到第m大的数后，扫描一次数组，比这个数大的都取出来就是了。这是O(n)的算法。
如果还要对这m个数排序，那么O(n)的就做不到了

flushtime 2007-10-11

打赏
举报

medie2005:

那个O(n)算法针对的问题是: 从n个数中找出第m大的....
现在的问题是: 取出前m大的.

flushtime 2007-10-11

打赏
举报

使用捅排序有个前提,就是数据的范围是O(n).
现在不知道数的范围,桶排序未必有用.

如果B -A = n^3
那捅排序的时间复杂度还会是O(n)吗?

超级大笨狼 2007-10-11

打赏
举报

从n个数中取前m大的数有什么好的算法吗？复杂度怎么样？
不考虑空间的话有O(n)的做法.

1,得到全部n中最大的数A,O(n).
2,得到全部n中最小的数B,O(n).
3,开辟一个数组Arr长度A-B,Arr[0]代表B,Arr[A-B]代表A
4,遍历n个数,找到对应下标放进去O(1).
5,按照下表依次输出m个数O(m).

单位操作步数:T=3*n+m,最终复杂度还是O(n)

超级大笨狼 2007-10-11

打赏
举报

O(m*log(n))

桶排序

medie2005 2007-10-11

打赏
举报

代码中的__unguarded_partition，就是一次枢轴分划函数：
分划区间为[first,last)，枢轴值为：
_Tp(__median(*__first, *(__first+(__last-__first)/2), *(__last-1))))，也就是区间[first,last)的前、中、后三处的中值。

medie2005 2007-10-11

打赏
举报

不是有O(n)的算法吗？

利用快速排序的枢轴分划思想，就可以得到一个O(n)的算法。

当然，代码实现不好的O(n)算法，在实践中的表现可能还赶不上实现高效的O(m*log(n))的算法。
好在C++的STL库中已经将它实现为nth_element了，直接用就是了。

附上STL的实现代码：

template   <class   _RandomAccessIter,   class   _Tp>   

void   __nth_element(_RandomAccessIter   __first,   _RandomAccessIter   __nth,   

					 _RandomAccessIter   __last,   _Tp*)   {   

	while   (__last   -   __first   >   3)   {   

		_RandomAccessIter   __cut   =   

			__unguarded_partition(__first,   __last,   

			_Tp(__median(*__first,   

			*(__first   +   (__last   -   __first)/2),   

			*(__last   -   1))));   

		if   (__cut   <=   __nth)   

			__first   =   __cut;   

		else     

			__last   =   __cut;   

	}   

	__insertion_sort(__first,   __last);   

}   



template   <class   _RandomAccessIter>   

inline   void   nth_element(_RandomAccessIter   __first,   _RandomAccessIter   __nth,   

							_RandomAccessIter   __last)   {   

	__nth_element(__first,   __nth,   __last,   __VALUE_TYPE(__first));   

}