如何用TopN算法在10億個(gè)整數(shù)中找出前1000個(gè)最大的數(shù)

如何用TopN算法在10億個(gè)整數(shù)中找出前1000個(gè)最大的數(shù)，相信很多沒有經(jīng)驗(yàn)的人對(duì)此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個(gè)問題。

面試題目：如何在10億個(gè)整數(shù)中找出前1000個(gè)最大的數(shù)。

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

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

2. 快速排序：選一個(gè)基準(zhǔn)元素，每次排序可以將這個(gè)基準(zhǔn)元素?cái)R置在正確的位置，左邊都是比基準(zhǔn)小的元素，右邊都是比基準(zhǔn)大的元素從而將數(shù)組分成左右兩部分，分而治之。TopN問題也同樣如此，選擇一個(gè)基準(zhǔn)元素并通過快速排序?qū)⒒鶞?zhǔn)元素?cái)R置在正確的位置，如果左邊的元素個(gè)數(shù)小于1000，那么繼續(xù)從基準(zhǔn)右邊排序，如果左邊元素個(gè)數(shù)大于1000，那么從基準(zhǔn)左邊排序，直到基準(zhǔn)的位置正好在1000，結(jié)束。
   缺點(diǎn)：第一次排序復(fù)雜度是O(n),第二次排序復(fù)雜度是O(n/2),第三次排序復(fù)雜度是O(n/4)....

3. 文件存儲(chǔ)，分而治之:

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

   缺點(diǎn)：磁盤讀取，寫入次數(shù)過多。

4. MapReduce:單機(jī)內(nèi)存和性能確實(shí)受限，那么我們可以將10億個(gè)分段存儲(chǔ)在不同的機(jī)器上，每臺(tái)機(jī)器計(jì)算各自的TopN，最后匯總。
   缺點(diǎn)：空間換時(shí)間。

最優(yōu)解：小頂堆

    在內(nèi)存中維護(hù)一個(gè)長(zhǎng)度為N的數(shù)組，根據(jù)堆的性質(zhì)，每一個(gè)節(jié)點(diǎn)都比他的左右子節(jié)點(diǎn)小，先取出前N個(gè)數(shù)并構(gòu)建小頂堆，然后將所有數(shù)據(jù)與堆頂比較大小，如果比堆頂小就直接丟棄，如果比堆頂大則替換堆頂，并且重新構(gòu)建這個(gè)堆。

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

具體執(zhí)行代碼如下：

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億個(gè)整數(shù)
    public static int arrs[] =  new int[LEN];
    public static int result[] = new int[N]; //在內(nèi)存維護(hù)一個(gè)長(zhǎng)度為N的小頂堆
    public static int len = result.length;
    //堆中元素的有效元素 heapSize<=len
    public static int heapSize = len;
    public static void main(String[] args) {
        //生成隨機(jī)數(shù)組
        for(int i = 0;i<LEN;i++){
            arrs[i] = new Random().nextInt(999999999);
        }

        //構(gòu)建初始堆
        for(int i =  0;i<N;i++){
            result[i] = arrs[i];
        }
        //構(gòu)建小頂堆
        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+"個(gè)數(shù)，求Top"+N+"，耗時(shí)"+(System.currentTimeMillis()-start)+"毫秒");
        print();
    }


    /**
     * 自底向上構(gòu)建小堆
     */
    public static void buildMinHeap(){
        int size = len / 2 -1 ; //最后一個(gè)非葉子節(jié)點(diǎn)
        for(int i = size;i>=0;i--){
            minHeap(i);
        }
    }

    /**
     * i節(jié)點(diǎn)為根及子樹是一個(gè)小堆
     * @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;
            //遞歸向下構(gòu)建堆
            minHeap(index);
        }
    }

    /**
     * 返回i節(jié)點(diǎn)的左孩子
     * @param i
     * @return
     */
    public static int left(int i){
        return 2*i;
    }

    /**
     * 返回i節(jié)點(diǎn)的右孩子
     * @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();
    }
}

看完上述內(nèi)容，你們掌握如何用TopN算法在10億個(gè)整數(shù)中找出前1000個(gè)最大的數(shù)的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！