題目描述

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

思路

Java中實(shí)現(xiàn)了PriorityQueue，是一個堆，默認(rèn)會按照自然順序進(jìn)行升序維護(hù)堆。
所以可以利用它創(chuàng)建兩個堆：大頂堆和小頂推。大頂堆的所有元素都要比小頂堆的元素?。?/p>

大頂堆 < 小頂堆

所以我們從數(shù)據(jù)流中讀取數(shù)據(jù)的時候，首先要往大頂堆中插入數(shù)據(jù)，然后再往小頂堆中插入數(shù)據(jù)。再以后的數(shù)據(jù)插入過程中，奇數(shù)個數(shù)，往大頂堆中插入，偶數(shù)個數(shù)，往下頂堆中插入，保證兩個堆中的數(shù)量差不大于1。
但是，在插入數(shù)據(jù)的時候，需要判斷：

• 個數(shù)為奇數(shù)時，應(yīng)該往大頂堆插入，需要判斷要插入的數(shù)據(jù)，是否大于小頂堆的堆頂元素，說明小堆頂?shù)膶斣貞?yīng)該出隊(duì)，入隊(duì)大頂堆中，而要插入的數(shù)據(jù)實(shí)際應(yīng)該入隊(duì)小頂堆；
• 個數(shù)為偶數(shù)時，應(yīng)該往小頂堆插入數(shù)據(jù)，需要判斷，要插入的數(shù)據(jù)，是否小于大頂堆的堆頂元素，說明大堆頂?shù)脑匾鲫?duì)，入隊(duì)小頂堆中，而要插入的數(shù)據(jù)實(shí)際應(yīng)該入隊(duì)大頂堆；

維護(hù)好了兩個堆，取中位數(shù)就很簡單了，如果個數(shù)是偶數(shù)，則取兩個堆頂元素的平均值即可；如果為奇數(shù)，直接取大頂堆的堆頂元素即可

算法

import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });
    int count = 0;
    public void Insert(Integer num) {
        count++;
        if((count&1) != 0) {
            if(!minQueue.isEmpty() && minQueue.peek() < num) {
                minQueue.offer(num);
                num = minQueue.poll();
            }
            maxQueue.offer(num);
        } else {
            if(!maxQueue.isEmpty() && num < maxQueue.peek()){
                maxQueue.offer(num);
                num = maxQueue.poll();
            }
            minQueue.offer(num);
        }
    }

    public Double GetMedian() {
        if(minQueue.isEmpty() && maxQueue.isEmpty()) {
            return 0d;
        }
        double result;
        if((count&1) == 0) {
            result =  (minQueue.peek() + maxQueue.peek()) /2.0;
        } else {
            result = maxQueue.peek();
        }
        return result;
    }


}