數據流中的中位數，確實輕敵了

作者：大賽 2021-06-29 19:24:42

開發前端

問題也很簡單，也就是一組數據，找出它的中位數，然后有所不同的是這組數據可能會新增一些其他數據，也就是要我們自己維護這么一個數據結構去盡量高效的完成它。

[[408159]]

本文轉載自微信公眾號「bigsai」，作者大賽。轉載本文請聯系bigsai公眾號。

前言

大家好，我是bigsai，今天忙到爆炸(暫不透露以后透露)，給大家分享一個巧妙的問題，五分鐘掌握。

今天在刷題時候，遇到一個hard問題，也是挺有意思，在劍指offer的第41題和力扣【數據流中的中位數】。

題目描述是這樣的：

中位數是有序列表中間的數。如果列表長度是偶數，中位數則是中間兩個數的平均值。

例如，

[2,3,4] 的中位數是 3

[2,3] 的中位數是 (2 + 3) / 2 = 2.5

設計一個支持以下兩種操作的數據結構：

void addNum(int num) - 從數據流中添加一個整數到數據結構中。

double findMedian() - 返回目前所有元素的中位數。

其實問題也很簡單，也就是一組數據，找出它的中位數，然后有所不同的是這組數據可能會新增一些其他數據，也就是要我們自己維護這么一個數據結構去盡量高效的完成它。

我打開這題力扣上的額描述，它好像就在誘惑我，告訴我什么!

然后我就以為真實的數據就在這個范圍，然后一頓操作猛如虎，一提交直接GG。不過這個問題是個非常好的問題，等到后面講，仔細先看看!

好了不多說了，我們進入正題，看看這個經典問題到底如何分析。

小白級別方法(無腦排序)

這個問題的解決老少皆宜，小白也有小白的方法，題不在難，能過就行(只對小白有效哇)。

一組數據存儲，我用數組、List都可以，而中位數，其實就是中間一個(偶數兩個均值)數，這個也好辦啊，排序啊!

一個ArrayList()海納百川(不定長數組可以存儲數據)，一行Arrays.sort()走天下。用編程語言中已經存在的集合和API可以輕松實現!

分析一下這個算法的時間復雜度，每次插入時候需要排序 nlogn，查詢時間近O(1);次數多的話時間復雜度還是蠻高的。

具體代碼為：

/** initialize your data structure here. */ 
public MedianFinder() { 
 
} 
 
List<Integer>list=new ArrayList<>(); 
public void addNum(int num) { 
    list.add(num); 
    list.sort(null); 
} 
public double findMedian() { 
    if(list.size()%2==1) 
        return list.get(list.size()/2); 
    else { 
        return (double) (list.get((list.size()-1)/2)+list.get(list.size()/2))/2; 
    }  
}

一看結果，2000+ms，這也是一種極限了，這種方法僅限于小白，只為求過。

大白級別的方法(插入排序)

大白比小白稍微強一點，比較它大一點嘛，懂得多一點。

大白看到：這個序列剛開始沒有!然后一點一點在原有的基礎上增加長度，如果每次都打亂排序那代價有點高!所以能不能復用上次已經排好序的結果?

這不就插入排序嘛!

每次新來元素相當于插入排序的最后一步使他有序，然后在插入……

這個流程每次插入的時候由兩個部分組成，查找和移動，其中查找花費O(n),插入也是O(n)。時間復雜度依然是O(n)。

可以維護常數表示數據總個數，查找中位數時候可以直接根據數量查找，時間復雜度為O(1).這樣的時間復雜度在插入上優化為O(n)相比O(nlogn)有很大的提升。

但是聰明的大白還能發現一些閃光點，數組前面有序的，只是插入最后一個元素需要鎖定在有序順序結構中的位置，線性一個個查找太耗時了哇!這明顯就是一個二分應用的場景么!可以使用二分法找到插入的位置，然后插入。

二分+插入的時間復雜度是多少呢?

記住，不是O(logn),二分查找每一次的時間復雜度確實是O(logn)，但插入操作的時間復雜度依舊是O(n),總的時間復雜度取最高量級 O(logn)+O(n)=O(n)。

所以這里以后如果遇到某個面試官問你：插入排序使用二分查找優化時間復雜度是多少?你一定要堅定的回答：是O(n2),從單詞操作來看，雖然查詢變為O(logn)但是插入依舊O(n)，所以n個數時間復雜度依舊為O(n2)。

好了既然解釋清楚,一頓操作猛如虎，直接上代碼：

class MedianFinder { 
 
    /** initialize your data structure here. */ 
    public MedianFinder() { 
 
    } 
    int arr[]=new int[50000]; 
    int count=0; 
    public void addNum(int num) { 
        int low=0,high=count-1; 
        while (low <= high) { 
            int mid = (low + high) / 2; 
            int midVal = arr[mid]; 
 
            if (midVal < num) 
                low = mid + 1; 
            else if (midVal > num) 
                high = mid-1 ; 
            else  
                low++; 
        } 
 
        for(int i=count-1;i>=low;i--){ 
            arr[i+1]=arr[i]; 
        } 
        arr[low]=num; 
        count++; 
    } 
    public double findMedian() { 
 
        if(count%2==1) 
            return arr[count/2]; 
        else  
            return (double) (arr[count/2-1]+arr[count/2])/2; 
    } 
}

提交之后，200+ms，比起前面小白的無腦排序優化了很多，但只擊敗了10%用戶，說明方法還是不夠好，還是很白。

大佬的解法(雙堆/優先隊列)

這個問題的話其實也能想出來，但是確實除了這個問題沒見到兩個隊這么玩的，也算是打開眼界一回。

在前面，我們講過堆排序和優先隊列的原理 ,里面詳細的講解了堆這種數據結構，我們簡單回顧一下堆：

堆是一種完全二叉樹(即最后一層從左向右存在節點連續)，因為是完全二叉樹我們經常用數組存儲，可以通過二叉樹下標轉換很好的鎖定位置進行交換。

堆分為大根堆和小根堆：

如果所有節點大于孩子節點值，那么這個堆叫做大根堆，堆的最大值在根節點。

如果所有節點小于孩子節點值，那么這個堆叫做小根堆，堆的最小值在根節點。

了解完這些基本解決這題就夠了，這里不需要知道堆、優先隊列的具體實現。但是堆和優先隊列，怎么應用到這個中位數查找呢?

這個就很巧妙了，我們將數據等半分到兩個堆中，其中一個是小根堆，一個是大根堆，小根堆存最大的一半數據，大的中最小的在堆頂;大根堆存最小的一半數據，小的中最大的在堆頂，中位數就只可能在兩個堆頂部分產生啦!

但是在具體實現過程中，也有很多需要注意的地方，再添加時候要先判斷和其中一個堆頂比較大小，應該加到哪一個堆(優先隊列)中，但是添加之后可能數值一直遞增很大或者數值一直遞減很小可能造成兩個堆元素數量不平衡，那么就要將其中少的加到多的中。

這里我在實現的時候約束小根堆的元素個數等于大根堆個數(偶數)或者等于大根堆個數加一(奇數)，在奇數情況就直接取小根堆頂返回即可。因為Java已經實現優先隊列，你不需要詳細實現其中細節(大佬可以試試參考以前我寫的優先隊列實現)。

分析這個時間復雜度，每個堆插入、刪除的時間復雜度級別是O(log n/2)，即使如果面臨元素平衡可能多操作兩次，但是時間復雜度還是O(logn)級別。比起O(n)快了不少，數據量越大體現越明顯。

具體代碼為：

class MedianFinder { 
 
    /** initialize your data structure here. */ 
    public MedianFinder() { 
 
    } 
    Queue<Integer>q1=new PriorityQueue<>();//小根堆 放大的數據 
    //大根堆 
    Queue<Integer>q2=new PriorityQueue<>(new Comparator<Integer>() { 
        @Override 
        public int compare(Integer o1, Integer o2) { 
            return o2-o1; 
        } 
    }); 
    public void addNum(int num) { 
       if(q1.isEmpty()) 
            q1.add(num); 
        else if(num>q1.peek()){//插入到小根堆 
            q1.add(num); 
           if (q1.size()>q2.size()+1){ 
              q2.add(q1.poll()); 
            } 
        } 
        else{//插入到大根堆 
            q2.add(num); 
            if (q2.size()>q1.size()){ 
            q1.add(q2.poll()); 
            } 
        } 
 
    } 
    public double findMedian() { 
        if(q1.size()==q2.size()) 
            return (double)(q1.peek()+q2.peek())/2; 
        else  
            return q1.peek(); 
    } 
}