如何用TopN算法在10億個整數中找出前1000個最大的數

如何用TopN算法在10億個整數中找出前1000個最大的數，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

面試題目：如何在10億個整數中找出前1000個最大的數。

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

1.  冒泡算法：通過兩層for循環，外層第一次循環找到數組中最大的元素放置在倒數第一個位置，第二次循環找到第二大的元素放置在倒數第二個位置。。。循環N次就可以找到TopN。
   缺點：冒泡排序內層循環需要大量交換元素。復雜度介于O(n)和O(n^2)之間。

2. 快速排序：選一個基準元素，每次排序可以將這個基準元素擱置在正確的位置，左邊都是比基準小的元素，右邊都是比基準大的元素從而將數組分成左右兩部分，分而治之。TopN問題也同樣如此，選擇一個基準元素并通過快速排序將基準元素擱置在正確的位置，如果左邊的元素個數小于1000，那么繼續從基準右邊排序，如果左邊元素個數大于1000，那么從基準左邊排序，直到基準的位置正好在1000，結束。
   缺點：第一次排序復雜度是O(n),第二次排序復雜度是O(n/2),第三次排序復雜度是O(n/4)....

3. 文件存儲，分而治之:

   將比基準小的元素存儲在txt1中，比基準大的文件存儲在txt2中，然后通過類似方法二的形式，最后求出TopN。

   缺點：磁盤讀取，寫入次數過多。

4. MapReduce:單機內存和性能確實受限，那么我們可以將10億個分段存儲在不同的機器上，每臺機器計算各自的TopN，最后匯總。
   缺點：空間換時間。

最優解：小頂堆

    在內存中維護一個長度為N的數組，根據堆的性質，每一個節點都比他的左右子節點小，先取出前N個數并構建小頂堆，然后將所有數據與堆頂比較大小，如果比堆頂小就直接丟棄，如果比堆頂大則替換堆頂，并且重新構建這個堆。

    構建小頂堆的過程：先要找到最后一個非葉子節點，數組的長度為6，那么最后一個非葉子節點就是：長度/2-1，也就是6/2-1=2，然后下一步就是比較該節點值和它的左右節點值，如果該節點大于其左\右子樹的值就交換（意思就是將最小的值放到該節點）。如果該節點不是葉子結點，則遞歸這一過程，直到這個節點變成葉子節點。

具體執行代碼如下：

import java.util.Random;

/**
 * @author vincent
 * @time 2019-08-07 11:59
 */
public class TopN {
    public static int N = 10;           //Top10
    public static int LEN = 100000000; //1億個整數
    public static int arrs[] =  new int[LEN];
    public static int result[] = new int[N]; //在內存維護一個長度為N的小頂堆
    public static int len = result.length;
    //堆中元素的有效元素 heapSize<=len
    public static int heapSize = len;
    public static void main(String[] args) {
        //生成隨機數組
        for(int i = 0;i<LEN;i++){
            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個最大的數的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！