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
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, ifA=[1,2,3], median is2. IfA=[1,19], median is1.
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].
Total run time in O(nlogn).
line 18, 23
>
= including 2
size() return type size_type it's unsigned integer
if doing subtracting on uint , will get undesired result
class Solution {
public:
/\*\*
\* @param nums: A list of integers.
\* @return: The median of numbers
\*/
vector<int> medianII\(vector<int> &nums\) {
// write your code here
vector<int> res;
priority\_queue<int> maxHeap;
priority\_queue<int, vector<int>, greater<int>> minHeap;
for \(auto &num : nums\) {
if \(maxHeap.empty\(\) \|\| num <= maxHeap.top\(\)\) {
maxHeap.push\(num\);
} else {
minHeap.push\(num\);
}
if \(maxHeap.size\(\) >= 2 + minHeap.size\(\)\) {
// balance
minHeap.push\(maxHeap.top\(\)\);
maxHeap.pop\(\);
}
if \(minHeap.size\(\) >= 2 + maxHeap.size\(\)\) {
// balance
maxHeap.push\(minHeap.top\(\)\);
minHeap.pop\(\);
}
if \(minHeap.size\(\) <= maxHeap.size\(\)\) {
res.push\_back\(maxHeap.top\(\)\);
} else {
res.push\_back\(minHeap.top\(\)\);
}
}
return res;
}
};