解法1:可以使用容量为K的最小堆来存储最大的K个数,最小堆的堆顶元素就是最大K个数中最小的一个。每次新考虑一个数X,如果X比堆顶的元素Y小,则不需要改变原来的堆。如果X比Y大,那么就用X替换堆顶的元素Y,并调整新的堆成为最小堆。调整堆的时间复杂度为O(log2K)。
这样的话,算法扫描所有的数据一次,总的时间复杂度为O(N*log2K)。
解法2:如果所有N个数都是正整数,并且它们的取值范围不太大,都在(0,MAXN)区间的话,可以考虑申请一个空间,例如数组count[MAXN],记录下每个整数出现的个数(count[i]表示整数i在所有整数中出现的个数)。我们只须扫描一遍就可以得到count数据,然后,从数组最后往前数出K个数就OK了。