找最大的N个数

题目：找最大的N个数

时间限制1000 ms，内存限制256000 kB，代码长度限制8000 B。

给定N个整数，找最大的前M个数(不一定有序)，要求时间复杂度尽量低。

先输入N和M (1 < = M < = N < = 50000)。然后下面N行每行代表一个整数（每个整数在int范围内），输出有M行，每行一个整数，表示最大的M个数。

输入示例：

5编程题-找最大的N个数

3

5

4

3

2

1

输出示例：

5

4

3

分析：1、如果所有的数据都可以装入内存，可以考虑使用快排中的分割函数Partition()，找到前M个最大的数，此时的平均复杂度是O(N)。

#include <stdio.h>#include <set>void GetGreatestNumber(){FILE *file;file = fopen("D:\\input.txt","r");if (file == NULL)return;unsigned int N, M;fscanf(file, "%d %d", &M, &N);std::multiset<int, std::less<int> > minHeap;for (unsigned int i = 0; i < M; ++ i){int num;fscanf(file,"%d", &num);if (minHeap.size() < N){minHeap.insert(num);}else{if (*(minHeap.begin()) < num){minHeap.erase(minHeap.begin());minHeap.insert(num);}}}std::multiset<int, std::less<int> >::reverse_iterator rIter;for (rIter = minHeap.rbegin();rIter != minHeap.rend();++ rIter){printf("%d\n", *rIter);}fclose(file);}

PS：有道，机试，2013，校招

参考：《剑指Offer》