你真的會寫無序數(shù)組中位數(shù)的查找算法嗎？PriorityQueue的妙用

??中位數(shù)（又稱中值，英語：Median），統(tǒng)計學(xué)中的專有名詞，代表一個樣本、種群或概率分布中的一個數(shù)值，其可將數(shù)值集合劃分為相等的上下兩部分。對于有限的數(shù)集，可以通過把所有觀察值高低排序后找出正中間的一個作為中位數(shù)。如果觀察值有偶數(shù)個，通常取最中間的兩個數(shù)值的平均數(shù)作為中位數(shù)。
??面試時，大家是不是經(jīng)常被問到，怎么求一個無序數(shù)組（長度為n）的中位數(shù)？

??面試官：知道什么是中位數(shù)嗎？

??我：知道啊。

??面試官：那你寫個中位數(shù)的求解方法吧。

??我：這還不簡單嗎？（內(nèi)心：這面試官怕是一個傻子額，這么簡單的問題還要問）。給我?guī)追昼姇r間。

??……

??幾分鐘之后，我把代碼給面試官看了一下，面試官一臉嫌棄的望著我。

??我的代碼如下：

public double getMedian(int[] arr){
        if(arr.length == 0)
            return 0;
        Arrays.sort(arr);
        int mid = arr.length / 2;

        if(arr.length%2 == 1)
            return arr[mid];
        else
            return (double)(arr[mid-1] + arr[mid])/2;
    }

??面試官：還有其他方法嗎？

??我：讓我再想一下……額，好像用二叉堆也可以實現(xiàn)，不過也不用自己實現(xiàn)二叉堆了，畢竟JDK里面有一個類已經(jīng)實現(xiàn)了二叉堆的數(shù)據(jù)結(jié)構(gòu)，正好可以借來用一用。

??于是，我給出了如下的代碼：

?????優(yōu)化后的代碼：

public double getMedian(int[] arr){
        int heapSize = arr.length/2 + 1;
        PriorityQueue<Integer> heap = new PriorityQueue<>(heapSize);
        for(int i=0; i<heapSize; i++){
            heap.add(arr[i]);
        }
        for(int i=heapSize; i<arr.length; i++){
            if(heap.peek()<arr[i]){
                heap.poll();
                heap.add(arr[i]);
            }
        }
        if(arr.length % 2 == 1){
            return (double)heap.peek();
        }
        else{
            return (double)(heap.poll()+heap.peek())/2.0;
        }
    }

??面試官突然眼前一亮，連連稱贊這個小伙子基礎(chǔ)還不錯。我感覺離入職又進了一步……

??最后，其實JDK里面已經(jīng)給我們封裝了很多好用的工具或者數(shù)據(jù)結(jié)構(gòu)，在知道原理的情況下去合理使用才能提高開發(fā)效率，也不一定什么輪子都要自己造。

??歡迎大家關(guān)注我的微信公眾號，不定期分享各類面試題。