Data Stream Median

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:

Using one max and one min ProrityQueues to store the lower part and upper part of the avaliable data. During the process, we need to keep the size of lower part is greater or equal to the size of upper part plus one.

The max number in the lower part would be the median.

Code:

public class Solution {

    public int[] medianII(int[] nums) {
        Queue<Integer> lower = new PriorityQueue<>(5, Collections.reverseOrder());
        Queue<Integer> upper = new PriorityQueue<>();
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            addNumToQ1(nums[i], lower, upper);
            res[i] = lower.peek();
        }
        return res;
    }

    private void addNumToQ(int x, Queue<Integer> lower, Queue<Integer> upper) {
        upper.offer(x);
        lower.offer(upper.poll());
        if (lower.size() > upper.size() + 1) {
            upper.offer(lower.poll());
        }
    }
}