0%

从10万个数中找10个最大的数

从10万个数中找10个最大的数

对于这种题目,最普通的想法是先对这10万个数进行排序,然后再选取数组中前10个数,即为最后的答案,排序算法的时间复杂度不下于O(N lgN)。最好的方法是建立一个最小堆。
算法描述:
我们首先取10万个元素中的前10个元素来建立由10个元素组成的最小堆。这样堆顶元素便是当前已知元素的第10大的数;然后依次读取剩下的99990个元素,若读取的元素比堆顶元素大,则将堆顶元素和当前元素替换,并自堆顶至下调整堆;这样读取完所有元素后,堆中的10个元素即为这10万个数最大的10个数,同时堆顶元素为这10万个元素第10大元素。
时间复杂度:
设从N个数中找M个最大数
每次重新恢复堆的时间复杂都为O(logM),最多供进行了(N-M)次恢复堆操作,顾时间复杂度为O(NlogM)。