Lintcode: Data Stream Median

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

Have you met this question in a real interview? 

Yes

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).

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.

//codes
http://www.jiuzhang.com/solutions/median-in-data-stream/
//how to use priority queue
https://github.com/kamyu104/LintCode/blob/master/C++/median-in-data-stream.cpp
Use two priority_queue to record input numbers
Time:O(nlogn)
Space: O(n)
p.s. change while in line 23/27, codes also work

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

class Solution { public: /** * @param nums: A list of integers. * @return: The median of numbers */ /* struct comp{ bool operator()(int x, int y) const { return x > y; } }; */ vector<int> medianII(vector<int> &nums) { vector<int> res; priority_queue<int> maxHeap; priority_queue<int, vector<int>, greater<int>> minHeap; for(int i = 0; i < nums.size(); i++){ if(maxHeap.empty() || minHeap.empty()) maxHeap.push(nums[i]); else if(nums[i] > minHeap.top()) minHeap.push(nums[i]); else maxHeap.push(nums[i]); while(maxHeap.size() < minHeap.size()){ maxHeap.push(minHeap.top()); minHeap.pop(); } while(maxHeap.size() > minHeap.size() + 1){ minHeap.push(maxHeap.top()); maxHeap.pop(); } res.push_back(maxHeap.top()); } return res; } };