题目来源
给一个数组以及移动窗口大小，从左边移到右边每次移一格，然后求每个窗口中数组的中位数。
我只能想到最简单的方法，就是每次都算一下中位数。
代码如下：
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<double> res(n - k + 1, 0);
bool even = (k % 2 == 0);
for (int i=0; i<=n-k; i++) {
vector<int> tmp(nums.begin()+i, nums.begin()+i+k);
sort(tmp.begin(), tmp.end());
if (even)
res[i] = (static_cast<double>(tmp[k/2]) + static_cast<double>(tmp[k/2-1])) / 2.0;
else
res[i] = tmp[k/2];
}
return res;
}
};
然后结果很显然，超时了…
然后我又去看了大神们的做法…
用multiset来做，每次插入删除并维持mid，时间复杂度O(nlogk)，我刚才那个应该是O(nklogk)。
代码如下：
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
multiset<int> windows(nums.begin(), nums.begin() + k);
auto mid = next(windows.begin(), k / 2);
vector<double> medians;
for (int i=k; ; i++) {
medians.push_back((static_cast<double>(*mid) + *prev(mid, 1 - k % 2)) / 2);
if (i == nums.size())
return medians;
windows.insert(nums[i]);
if (nums[i] < *mid)
mid--;
if (nums[i-k] <= *mid)
mid++;
windows.erase(windows.lower_bound(nums[i-k]));
}
}
};
