Median II

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

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

O(nlogn) time

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.

 
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of numbers
     */
    vector<int> medianII(vector<int> &nums) {
       priority_queue<int> maxHeap;
       priority_queue<int, vector<int>, greater<int>> minHeap;
       
       vector<int> ret;
       for(int i = 0; i < nums.size(); i++) {
            int tmp = nums[i];
            if (i & 1) {
                if (maxHeap.top() > tmp) {
                    maxHeap.push(tmp);
                    tmp = maxHeap.top();
                    maxHeap.pop();
                }
                minHeap.push(tmp);
            }
            else
            {
                if (minHeap.size() > 0 && minHeap.top() < tmp) {
                    minHeap.push(tmp);
                    tmp = minHeap.top();
                    minHeap.pop();
                }
                
                maxHeap.push(tmp);
            }
            
            ret.push_back(maxHeap.top());
       }
       
       
       return ret;
    }
};