題目來源
給一個數(shù)組以及移動窗口大小忧便，從左邊移到右邊每次移一格，然后求每個窗口中數(shù)組的中位數(shù)茫叭。
我只能想到最簡單的方法镣煮，就是每次都算一下中位數(shù)。
代碼如下：
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;
}
};
然后結(jié)果很顯然恃锉，超時了…
然后我又去看了大神們的做法…
用multiset來做，每次插入刪除并維持mid，時間復(fù)雜度O(nlogk)眼刃，我剛才那個應(yīng)該是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]));
}
}
};
