如何用TopN算法在10亿个整数中找出前1000个最大的数

如何用TopN算法找出10亿个整数中最大的前1000个数字，相信很多没有经验的人对此无能为力。因此，本文总结了出现问题的原因和解决方法，希望大家可以通过这篇文章来解决这个问题。

面试题目：如何在10亿个整数中找出前1000个最大的数字。

我们知道有很多排序算法：

冒泡算法：通过两层for循环，外循环找到数组中最大的元素，第一次放在倒数第二的位置，第二次循环找到第二大的元素，放在倒数第二的位置。循环n次找到TopN。

缺点：冒泡排序内循环需要大量的交换元素。复杂性介于0(n)和0(N2)之间。

快速排序：选择一个基准元素，在每次排序中可以放在正确的位置。左边的元素比基准小，右边的元素比基准大，这样数组就可以分为左右两部分。TopN问题也是如此。选择一个基准元素，并通过快速排序将其放在正确的位置。如果左边的元素数量少于1000，那么从基准的右边继续排序。如果左边的元素数量超过1000，那么从基准的左边开始排序，直到基准的位置正好是1000。

缺点：第一排序复杂度为O(n)，第二排序复杂度为O(n/2)，第三排序复杂度为O(n/4)。

文件存储，分而治之：

小于基准的元素存储在txt1中，大于基准的文件存储在txt2中。然后，以类似于方法2的方式，最终获得TopN。

缺点：磁盘读写次数太多。

MapReduce:的内存和性能确实有限，所以我们可以在不同的机器上存储10亿段，每台机器计算自己的TopN，最后总结出来。

缺点：以空间换时间。

00-1010，长度为n的数组保存在内存中。根据堆的性质，每个节点都小于它的左右子节点。首先，取出前n个数字，构建一个小的顶部堆，然后将所有数据与堆顶部进行比较。如果小于堆顶，则直接丢弃；如果它更大，它将替换堆顶部并重建堆。

构建小顶堆的过程：首先找到最后一个非叶节点，数组的长度是6，然后最后一个非叶节点是长度/2-1,也就是6/2-1=2，然后下一步是比较这个节点的值和它的左右节点值，如果这个节点的值大于它的左\右子树的值(意思是把最小值放在这个节点中)就交换。如果该节点不是叶节点，则重复该过程，直到该节点成为叶节点。

具体执行代码如下：

import Java . util . random；

/**

*@authorvincent

*@time2019-08-0711:59

*/

publicclassTopN{

publicationstatintn=10；//Top10

publicationstatintlen=100000000；//1亿个整数。

publicationstatintarrs[]=new int[LEN]；

publicationstationresult[]=new int[N]；//在内存中维护一个长度为n的小顶堆。

publicationstatintlen=result . length；

//堆中元素的有效元素heapSize=len。

publicationstatinthesize=len；

publicationstativitmain(String[]args){ 0

//生成随机数组。

for(inti=0；iLENI){ 0

铌

sp;       arrs[i] = new Random().nextInt(999999999);
        }
        //构建初始堆
        for(int i =  0;i<N;i++){
            result[i] = arrs[i];
        }
        //构建小顶堆
        long start =System.currentTimeMillis();
        buildMinHeap();
        for(int i = N;i<LEN;i++){
            if(arrs[i] > result[0]){
                result[0] = arrs[i];
                minHeap(0);
            }
        }
        System.out.println(LEN+"个数，求Top"+N+"，耗时"+(System.currentTimeMillis()-start)+"毫秒");
        print();
    }
    /**
     * 自底向上构建小堆
     */
    public static void buildMinHeap(){
        int size = len / 2 -1 ; //最后一个非叶子节点
        for(int i = size;i>=0;i–){
            minHeap(i);
        }
    }
    /**
     * i节点为根及子树是一个小堆
     * @param i
     */
    public static void minHeap(int i){
        int l = left(i);
        int r = right(i);
        int index = i;
        if(l<heapSize && result[l]< result[index]){
            index = l;
        }
        if(r<heapSize && result[r]< result[index]){
            index = r;
        }
        if(index != i){
            int t = result[index];
            result[index] = result[i];
            result[i] = t;
            //递归向下构建堆
            minHeap(index);
        }
    }
    /**
     * 返回i节点的左孩子
     * @param i
     * @return
     */
    public static int left(int i){
        return 2*i;
    }
    /**
     * 返回i节点的右孩子
     * @param i
     * @return
     */
    public static int right(int i){
        return 2*i+1;
    }
    /**
     * 打印
     */
    public  static void print(){
        for(int a: result){
            System.out.print(a+",");
        }
        System.out.println();
    }
}

看完上述内容，你们掌握如何用TopN算法在10亿个整数中找出前1000个最大的数的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注行业资讯频道，感谢各位的阅读！