[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