输入n个整数,输出其中最大的k个。例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为5,6,7和8。
解法一
开一个容量为K的最小堆。每次来一个数,比较堆顶(最小值)和这个数谁大,如果当前的数更大,就替换掉堆顶。时间复杂度 \(O(n \log k)\)
优点:对于海量数据(流),可以用\(O(k)\)的内存搞定
缺点:堆的实现略复杂,建议直接用STL
解法二
用QuickSelect(快速选择)算法,是基于快排的一种变体,平均复杂度为 \(O(n)\)
优点:平均情况下速度快
缺点:需要保存所有输入数据,并且会修改输入数据,对于海量数据不合适。
代码
包含一些测试写在main()里。
1 |
|
结果
\(n=10^6, k=1000\)