Median II

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.

----------------------------- thinking ----------------------------------
Bug -> we need to consider the equal numbers in the codes

Attention!!!! the usage of priority queue in this question

http://blog.csdn.net/nicaishibiantai/article/details/43634367
------------------------------- codes ---------------------------------------
class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: The median of numbers
     */
    vector<int> medianII(vector<int> &nums) {
        // write your code here
        priority_queue<int, vector<int>, greater<int>> minheap;
        priority_queue<int> maxheap;
        vector<int> result(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            if (minheap.size() == maxheap.size()) {
                if (minheap.size() == 0) {
                    result[i] = nums[i];
                    maxheap.push(nums[i]);
                } else {
                    if (nums[i] >= maxheap.top() && nums[i] <= minheap.top()) {
                        result[i] = nums[i];
                        maxheap.push(nums[i]);
                    } else if (nums[i] < maxheap.top()) {
                        result[i] = maxheap.top();
                        maxheap.push(nums[i]);
                    } else {
                        result[i] = minheap.top();
                        maxheap.push(minheap.top());
                        minheap.pop();
                        minheap.push(nums[i]);
                    }
                }
            } else {
                if (nums[i] >= maxheap.top()) {
                    result[i] = maxheap.top();
                    minheap.push(nums[i]);
                } else {
                    maxheap.push(nums[i]);
                    minheap.push(maxheap.top());
                    maxheap.pop();
                    result[i] = maxheap.top();
                }
            }
        }
        return result;
    }
};