題目描述
如何得到一個(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ù)的時(shí)間效率都高效，這里使用大頂堆+小頂堆的容器，并且滿足：

1、兩個(gè)堆中的數(shù)據(jù)數(shù)目差不能超過(guò)1，這樣可以使中位數(shù)只會(huì)出現(xiàn)在兩個(gè)堆的交接處；

2、大頂堆的所有數(shù)據(jù)都小于小頂堆，這樣就滿足了排序要求。

注：PriorityQueue 是從JDK1.5開始提供的新的數(shù)據(jù)結(jié)構(gòu)接口，默認(rèn)內(nèi)部是自然排序，結(jié)果為小頂堆

解釋說(shuō)明：

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {

/* 大頂堆，存儲(chǔ)左半邊元素 */
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
/* 小頂堆，存儲(chǔ)右半邊元素，并且右半邊元素都大于左半邊 */
private PriorityQueue<Integer> right = new PriorityQueue<>();
/* 當(dāng)前數(shù)據(jù)流讀入的元素個(gè)數(shù) */
private int N = 0;

public void Insert(Integer val) {
    /* 插入要保證兩個(gè)堆存于平衡狀態(tài) */
    if (N % 2 == 0) {
        /* N 為偶數(shù)的情況下插入到右半邊。
         * 因?yàn)橛野脒呍囟家笥谧蟀脒?，但是新插入的元素不一定比左半邊元素?lái)的大，
         * 因此需要先將元素插入左半邊，然后利用左半邊為大頂堆的特點(diǎn)，取出堆頂元素即為最大元素，此時(shí)插入右半邊 */
        left.add(val);
        right.add(left.poll());
    } else {
        right.add(val);
        left.add(right.poll());
    }
    N++;
}

public Double GetMedian() {
    if (N % 2 == 0)
        return (left.peek() + right.peek()) / 2.0;
    else
        return (double) right.peek();
}


}