如何得到一个数据流中的中位数

Question

如题所述

Answer 1

对于数据流，对应的就是在线算法了，一道很经典的题目就是在1亿个数中找到最大的前100个数，这是一道堆应用题，找最大的前100个数，那么我们就创建一个大小为100的最小化堆，每来一个元素就与堆顶元素比较，因为堆顶元素是目前前100大数中的最小数，前来的元素如果比该元素大，那么就把原来的堆顶替换掉。

那么对于这一道题呢？如果单纯的把所有元素放到一个数组里，每次查找中位数最快也要O(n)，综合下来是O(n^2)的复杂度。我们可以利用上面例子中的想法，用一个最大堆来维护当前前n/2小的元素，那么每次找中位数只到取出堆顶就可以了。但是，有一个问题，数据要动态增长，有可能之前被替换掉的元素随着元素的增加又跑回来了，所以我们不能单纯得向上题一样把元素丢掉，我们可以再用一个最小化堆来存前n/2大的元素。

class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of the element inside the window at each moving
*/
vector<int> medianSlidingWindow(vector<int> &nums, int k) {
// write your code here
vector<int> res;
if (k > nums.size() || k == 0) return res;
multiset<int> left, right;
//init heaps by first kth elements in nums
for (int i = 0; i < k; ++i) {
left.insert(nums[i]);
}
while (left.size() > (k + 1) / 2) {
right.insert(*left.rbegin());
left.erase(left.find(*left.rbegin()));
}
res.push_back(*left.rbegin());
//slide window
for (int i = k; i < nums.size(); ++i) {
//delete the leftmost element in window from heaps
if (nums[i-k] > res.back()) right.erase(right.find(nums[i-k]));
else left.erase(left.find(nums[i-k]));
//insert new element into heaps
if (!left.empty() && nums[i] <= *left.rbegin()) left.insert(nums[i]);
else right.insert(nums[i]);
//adjust heaps so that the left heap contains (k + 1) / 2 elements
while (left.size() < (k + 1) / 2) {
left.insert(*right.begin());
right.erase(right.begin());
}
while (left.size() > (k + 1) / 2) {
right.insert(*left.rbegin());
left.erase(left.find(*left.rbegin()));
}
res.push_back(*left.rbegin());
}
return res;
}
};