[leetcode/lintcode 題解]大廠面試真題：資料流中位數

數字是不斷進入數組的，在每次添加一個新的數進入數組的同時傳回目前新數組的中位數。

說明

中位數的定義：

• 這裡的中位數不等同于數學定義裡的中位數。
• 中位數是排序後數組的中間值，如果有數組中有n個數，則中位數為A[(n−1)/2]。
• 比如：數組A=[1,2,3]的中位數是2，數組A=[1,19]的中位數是1。

線上評測位址：

領扣官網

樣例1

輸入: [1,2,3,4,5]
輸出: [1,1,2,2,3]
樣例說明：
[1] 和 [1,2] 的中位數是 1.
[1,2,3] 和 [1,2,3,4] 的中位數是 2.
[1,2,3,4,5] 的中位數是 3.           

樣例2

輸入: [4,5,1,3,2,6,0]
輸出: [4,4,4,3,3,3,3]
樣例說明：
[4], [4,5] 和 [4,5,1] 的中位數是 4.
[4,5,1,3], [4,5,1,3,2], [4,5,1,3,2,6] 和 [4,5,1,3,2,6,0] 的中位數是 3.           

題解

用 maxheap 儲存左半部分的數，用 minheap 儲存右半部分的數。 把所有的數一左一右的加入到每個部分。左邊部分最大的數就一直都是 median。 這個過程中，可能會出現左邊部分并不完全都 <= 右邊部分的情況。這種情況發生的時候，交換左邊最大和右邊最小的數即可。

public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: the median of numbers
     */
    private PriorityQueue<Integer> maxHeap, minHeap;
    private int numOfElements = 0;

    public int[] medianII(int[] nums) {
        // write your code here
        Comparator<Integer> revCmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer left, Integer right) {
                return right.compareTo(left);
            }
        };
        int cnt = nums.length;
        maxHeap = new PriorityQueue<Integer>(cnt, revCmp);
        minHeap = new PriorityQueue<Integer>(cnt);
        int[] ans = new int[cnt];
        for (int i = 0; i < cnt; ++i) {
            addNumber(nums[i]);
            ans[i] = getMedian();
        }
        return ans;
    }
    void addNumber(int value) {
        maxHeap.add(value);
        if (numOfElements%2 == 0) {
            if (minHeap.isEmpty()) {
                numOfElements++;
                return;
            }
            else if (maxHeap.peek() > minHeap.peek()) {
                Integer maxHeapRoot = maxHeap.poll();
                Integer minHeapRoot = minHeap.poll();
                maxHeap.add(minHeapRoot);
                minHeap.add(maxHeapRoot);
            }
        }
        else {
            minHeap.add(maxHeap.poll());
        }
        numOfElements++;
    }
    int getMedian() {
        return maxHeap.peek();
    }
}           

更多題解參考：

九章官網Solution