本文首發(fā)于我的個(gè)人博客：尾尾部落

題目描述

如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)。

解題思路

我們可以將數(shù)據(jù)排序后分為兩部分，左邊部分的數(shù)據(jù)總是比右邊的數(shù)據(jù)小。那么，我們就可以用最大堆和最小堆來(lái)裝載這些數(shù)據(jù)：

• 最大堆裝左邊的數(shù)據(jù)，取出堆頂（最大的數(shù)）的時(shí)間復(fù)雜度是O(1)
• 最小堆裝右邊的數(shù)據(jù)，同樣，取出堆頂（最小的數(shù)）的時(shí)間復(fù)雜度是O(1)

從數(shù)據(jù)流中拿到一個(gè)數(shù)后，先按順序插入堆中：如果左邊的最大堆是否為空或者該數(shù)小于等于最大堆頂?shù)臄?shù)，則把它插入最大堆，否則插入最小堆。然后，我們要保證左邊的最大堆的size等于右邊的最小堆的size或者最大堆的size比最小堆的size大1。
要獲取中位數(shù)的話，直接判斷最大堆和最小堆的size，如果相等，則分別取出兩個(gè)堆的堆頂除以2得到中位數(shù)，不然，就是最大堆的size要比最小堆的size大，這時(shí)直接取出最大堆的堆頂就是我們要的中位數(shù)。

參考代碼

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
    // 最小堆（右）
    private PriorityQueue<Integer> rHeap = new PriorityQueue<>(); 
    // 最大堆（左）
    private PriorityQueue<Integer> lHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
    // 保證lHeap.size()>=rHeap.size()
    public void Insert(Integer num) {
        // 先按大小插入，再調(diào)整
        if(lHeap.isEmpty() || num <= lHeap.peek())
            lHeap.offer(num);
        else
            rHeap.offer(num);
        
        if(lHeap.size() < rHeap.size()){
            lHeap.offer(rHeap.peek());
            rHeap.poll();
        }else if(lHeap.size() - rHeap.size() == 2){
            rHeap.offer(lHeap.peek());
            lHeap.poll();
        }
    }
    public Double GetMedian() {
        if(lHeap.size() > rHeap.size())
            return new Double(lHeap.peek());
        else
            return new Double(lHeap.peek() + rHeap.peek())/2;
    }
}