觅最大的N个数

找最大的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)。

void GetGreatestNum(int *input, int n, int*output, int k) {
    if (!input || !output || n <= 0 || k <= 0 || k > n) return;
    int start = 0;
    int end = n - 1;
    int index = Partition(input, n, start, end);
    while (index != k - 1) {
        if (index > k - 1) 
            end = index - 1;
        else 
            start = index + 1;
        index = Partition(input, n, start, end);
    }
    
    for (int i = 0; i < k; ++ i) 
        output[i] = input[i];
}

void Swap(int *a, int *b) {
    int temp = *a; *a = *b; *b = temp;
}

int Partition(int *data, int length, int start, int end) {
    // 大数在前，小数在后
    if (data == NULL || length <= 0 || start < 0 || end >= n) 
        throw new std::exception("Invalid Parameters");
    int index = RandomInRange(start, end);
    Swap(&data[index], &data[end]);
    int small = start - 1;
    for (index = data[start]; index <= end; ++ index) {
        if (data[index] > data[end]) {
            ++ small;
            if (small != index)
                Swap(&data[index], &data[small]);
        }
    }
    ++ small;
    Swap(&data[small], &data[end]);
    
    return small;
}

2、如果是大数据的情况，要考虑使用小顶堆来实现，每次比较堆顶元素和新元素的大小，若堆顶元素小，交换两元素，重建最小堆。此时的复杂度为O(N log M)。STL容器中set、multiset是基于红黑树来实现的，可以直接用其来实现最小堆。

#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》