NC395. 滑动窗口中位数
描述
示例1
输入:
[4,5,9,7,8,5],3
输出:
[5,7,8,7]
示例2
输入:
[4,5,9,7,8,5],4
输出:
[6,7.5,7.5]
C++ 解法, 执行用时: 76ms, 内存消耗: 7728KB, 提交时间: 2022-05-25
class DualHeap {
private:
// 大根堆，维护较小的一半元素
priority_queue<int> small;
// 小根堆，维护较大的一半元素
priority_queue<int, vector<int>, greater<int>> large;
// 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数
unordered_map<int, int> delayed;
int k;
// small 和 large 当前包含的元素个数，需要扣除被「延迟删除」的元素
int smallSize, largeSize;
public:
DualHeap(int _k): k(_k), smallSize(0), largeSize(0) {}
private:
// 不断地弹出 heap 的堆顶元素，并且更新哈希表
template<typename T>
void prune(T& heap) {
while (!heap.empty()) {
int num = heap.top();
if (delayed.count(num)) {
--delayed[num];
if (!delayed[num]) {
delayed.erase(num);
}
heap.pop();
}
else {
break;
}
}
}
// 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
void makeBalance() {
if (smallSize > largeSize + 1) {
// small 比 large 元素多 2 个
large.push(small.top());
small.pop();
--smallSize;
++largeSize;
// small 堆顶元素被移除，需要进行 prune
prune(small);
}
else if (smallSize < largeSize) {
// large 比 small 元素多 1 个
small.push(large.top());
large.pop();
++smallSize;
--largeSize;
// large 堆顶元素被移除，需要进行 prune
prune(large);
}
}
public:
void insert(int num) {
if (small.empty() || num <= small.top()) {
small.push(num);
++smallSize;
}
else {
large.push(num);
++largeSize;
}
makeBalance();
}
void erase(int num) {
++delayed[num];
if (num <= small.top()) {
--smallSize;
if (num == small.top()) {
prune(small);
}
}
else {
--largeSize;
if (num == large.top()) {
prune(large);
}
}
makeBalance();
}
double getMedian() {
return k & 1 ? small.top() : ((double)small.top() + large.top()) / 2;
}
};
class Solution {
public:
vector<double> slidewindow(vector<int>& nums, int k) {
DualHeap dh(k);
for (int i = 0; i < k; ++i) {
dh.insert(nums[i]);
}
vector<double> ans = {dh.getMedian()};
for (int i = k; i < nums.size(); ++i) {
dh.insert(nums[i]);
dh.erase(nums[i - k]);
ans.push_back(dh.getMedian());
}
return ans;
}
};
C++ 解法, 执行用时: 85ms, 内存消耗: 5820KB, 提交时间: 2022-07-20
class Solution {
public:
vector<double> slidewindow(vector<int>& nums, int k) {
vector<double> v;
multiset<int> t(nums.begin(), nums.begin() + k);
auto f = next(t.begin(), k / 2);
for (int i = k; ; i++) {
v.push_back((double(*f) + *prev(f, 1 - k % 2)) / 2);
if (i == nums.size())
return v;
t.insert(nums[i]);
if (nums[i] < *f)
f--;
if (nums[i - k] <= *f)
f++;
t.erase(t.lower_bound(nums[i - k]));
}
}
};
C++ 解法, 执行用时: 85ms, 内存消耗: 5820KB, 提交时间: 2022-05-19
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param k int整型
* @return double浮点型vector
*/
vector<double> slidewindow(vector<int>& nums, int k) {
// write code here
vector<double> result;
multiset<int> window(nums.begin(), nums.begin() + k);
auto mid = next(window.begin(), k / 2);
for (int i = k; ; i++)
{
result.push_back((double(*mid) + *prev(mid, 1 - k % 2)) / 2);
if (i == nums.size())
return result;
window.insert(nums[i]);
if (nums[i] < *mid)
mid--;
if (nums[i - k] <= *mid)
mid++;
window.erase(window.lower_bound(nums[i - k]));
}
}
};
C++ 解法, 执行用时: 88ms, 内存消耗: 5916KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param k int整型
* @return double浮点型vector
*/
vector<double> slidewindow(vector<int>& nums, int k) {
// write code here
vector<double> v;
multiset<int> t(nums.begin(),nums.begin()+k);
auto f=next(t.begin(),k/2);
for(int i=k;;i++)
{
v.push_back((double(*f)+*prev(f,1-k%2))/2);
if(i==nums.size())
return v;
t.insert(nums[i]);
if(nums[i]<*f)
f--;
if(nums[i-k]<=*f)
f++;
t.erase(t.lower_bound(nums[i-k]));
}
}
};
C++ 解法, 执行用时: 91ms, 内存消耗: 7732KB, 提交时间: 2022-04-22
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @param k int整型
* @return double浮点型vector
*/
/*int indexOf(vector<int>& src, const int target) {
int result = -1;
for (int i = 0; i < src.size(); i++) {
if (src[i] == target) {
result = i;
break;
}
}
return result;
}
void setBottleVisited(vector<int>& sorted_array, vector<bool>& bottle,
int target) {
int i = 0;
while (i < bottle.size()) {
if (sorted_array[i] == target && !bottle[i]) {
bottle[i] = true;
return;
}
i++;
}
}
//现在版本中的题解网站:https://www.bilibili.com/video/BV1dv4y1o7Un?spm_id_from=333.337.search-card.all.click
//这题在力扣上用这种类暴力题解是能通过的，牛客上通过不了，如果正确的方法要用
//优先队列双堆，一个large一个small来控制
vector<double> slidewindow(vector<int>& nums, int k) {
// write code here
if (nums.size() < k) {
return vector<double>();
}
vector<double> result;
vector<int> sorted_array = nums;
sort(sorted_array.begin(), sorted_array.end());
vector<bool> bottle(nums.size(), false);
int left = 0, right = k - 1;
//刚开始的时候先把[left,right-1]的所有元素对应的下标置为true
for (int i = left; i < right; i++) {
int targetIndex = indexOf(sorted_array, nums[i]);
//这里要注意:找到的targetIndex可能是已经被置为true了，因此要接下来往后移动一个进行查找
while(bottle[targetIndex]){
targetIndex++;
}
bottle[targetIndex] = true;
}
while (right < nums.size()) {
//当前滑动窗口内新的元素right在其中置为true
int rightIndexInSortedArray = indexOf(sorted_array, nums[right]);
while(bottle[rightIndexInSortedArray]){
rightIndexInSortedArray++;
}
bottle[rightIndexInSortedArray] = true;
//找中位数
if (k % 2 == 1) {
int i = 0;
int cnt = 0;
while (i < bottle.size()) {
if (bottle[i]) {
cnt++;
}
if (cnt == (k / 2 + 1)) {
result.push_back(sorted_array[i]);
break;
}
i++;
}
} else {
double sum = 0;
int i = 0;
int cnt = 0;
while (i < bottle.size()) {
if (bottle[i]) {
cnt++;
if (cnt == (k / 2)) {
sum = sum + sorted_array[i];
} else if (cnt == (k / 2 + 1)) {
sum = sum + sorted_array[i];
break;
}
}
i++;
}
result.push_back(sum * 1.0 / 2);
}
//清空left指向的这个数，因为下一次用不到了
int leftIndexInSorted = indexOf(sorted_array, nums[left]);
while(!bottle[leftIndexInSorted]){
leftIndexInSorted++;
}
bottle[leftIndexInSorted] = false;
left++;
right++;
}
return result;
}*/
//真正的题解
//网站:https://blog.csdn.net/weixin_43601103/article/details/113587918
priority_queue<int> small;
priority_queue<int, vector<int>, greater<int>> large;
int smallSize = 0, largeSize = 0;
unordered_map<int, int> ma;
template<typename T>
void prune(T& heap) {
while (!heap.empty()) {
int x = heap.top();
if (!ma.count(x)) break;
ma[x]--;
if (ma[x] == 0) {
ma.erase(x);
}
heap.pop();
}
}
void makeBalance() {
if (smallSize >= largeSize + 2) {
large.push(small.top());
small.pop();
smallSize--;
largeSize++;
prune(small);
} else if (smallSize < largeSize) {
small.push(large.top());
large.pop();
smallSize++;
largeSize--;
prune(large);
}
}
void insert(int x) {
if (small.empty() || x <= small.top()) {
small.push(x);
smallSize++;
} else {
large.push(x);
largeSize++;
}
makeBalance();
}
void Delete(int x) {
ma[x]++;
if (x <= small.top()) {
smallSize--;
if (x == small.top()) {
prune(small);
}
} else {
largeSize--;
if (x == large.top()) {
prune(large);
}
}
makeBalance();
}
double getMedian(int k) {
return k & 1 ? small.top() : ((double) small.top() + large.top()) / 2;
}
vector<double> slidewindow(vector<int>& nums, int k) {
int n = nums.size();
for (int i = 0; i < k; i++) {
insert(nums[i]);
}
vector<double> res = {getMedian(k)};
for (int i = k; i < n; i++) {
insert(nums[i]);
Delete(nums[i - k]);
res.push_back(getMedian(k));
}
return res;
}
};