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

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

??面試官：知道什么是中位數嗎？

??我：知道啊。

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

??我：這還不簡單嗎？（內心：這面試官怕是一個傻子額，這么簡單的問題還要問）。給我幾分鐘時間。

??……

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

??我的代碼如下：

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;
    }

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

??我：讓我再想一下……額，好像用二叉堆也可以實現，不過也不用自己實現二叉堆了，畢竟JDK里面有一個類已經實現了二叉堆的數據結構，正好可以借來用一用。

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

?????優化后的代碼：

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;
        }
    }

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

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

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