Data Stream Median 81

Question

Numbers keep coming, return the median of numbers at every time a new number added.

Clarification

What's the definition of Median?

• Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n - 1) / 2]. For example, if A=[1,2,3], median is 2. If A=[1,19], median is 1.

Example

For numbers coming list: [1, 2, 3, 4, 5], return [1, 1, 2, 2, 3].

For numbers coming list: [4, 5, 1, 3, 2, 6, 0], return [4, 4, 4, 3, 3, 3, 3].

For numbers coming list: [2, 20, 100], return [2, 2, 20].

Challenge

Total run time in O(nlogn).

Solution

用一个最大堆（MaxHeap）来存到达的有所元素中较小的一半，用一个最小堆（MinHeap）来存到达的所有元素中较大的一半。每次来一个新的元素就先加入MaxHeap，偶数次加入MaxHeap（不变），奇数次将MaxHeap堆顶元素（最大值）移到MinHeap中。在偶数次时，若MaxHeap堆顶元素（较小一半的最大值）比MinHeap堆顶元素（较大一半的最小值）大，则交换两者位置。median为MaxHeap堆顶元素。

代码如下：

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

    public int[] medianII(int[] nums) {
        // write your code here
        if(nums == null || nums.length <= 1){
            return nums;
        }
        //重构比较方法，使其从大到小排
        Comparator<Integer> revComp = new Comparator<Integer>(){
            public int compare(Integer left, Integer right){
                return right.compareTo(left);
            }
        };

        int length = nums.length;
        //维护一个最大堆和一个最小堆。
        maxHeap = new PriorityQueue<Integer>(length, revComp);
        minHeap = new PriorityQueue<Integer>(length);

        int[] result = new int[length];
        for(int i = 0; i < length; i++){
            addNumber(nums[i]);
            result[i] = getMedian();
        }

        return result;
    }

    private void addNumber(int value){
        maxHeap.add(value);
        if(numberOfElement % 2 == 0){
            if(minHeap.isEmpty()){
                numberOfElement++;
                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());
        }
        numberOfElement++;
    }

    private int getMedian(){
        return maxHeap.peek();
    }
}