Description:
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
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.
Solution:
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of numbers
*/
vector<int> medianII(vector<int> &nums) {
vector<int> rc;
auto sz = (int)nums.size();
if (sz == 0) return rc;
multiset<int> left, right;
for (int i = 0; i < sz; ++i) {
if (left.size() == right.size()) {
if (!right.empty() && nums[i] > *right.begin()) {
left.insert(*right.begin());
right.erase(right.begin());
right.insert(nums[i]);
} else
left.insert(nums[i]);
} else {
if (nums[i] < *left.rbegin()) {
right.insert(*left.rbegin());
left.erase(prev(end(left)));
left.insert(nums[i]);
} else
right.insert(nums[i]);
}
rc.push_back(*left.rbegin());
}
return rc;
}
};
转载于:https://www.cnblogs.com/deofly/p/data-stream-median.html
相关资源：JAVA上百实例源码以及开源项目
