C ++中的滑动窗口
假设我们有一个数字列表，并且有一个窗口大小k，我们必须使用滑动窗口方式找到中位数列表。因此，如果分布如下所示-
这里我们考虑了k为3，结果将为[1，-1，-1,3,5,6]
为了解决这个问题，我们将遵循以下步骤-
定义一组arr
定义一个函数insert()，它将取x，
将x插入arr
定义一个函数delete_()，它将取x，
从arr删除x（如果存在）
定义功能getMedian()
n：=arr的大小
a：=跳转到n/2–arr的第一个元素的前一级，并获取值
b：=跳转到arr的第一个元素的n/2向前，并获取值
如果arr的大小，则-
返回b
回报（a+b）*0.5
从主要方法执行以下操作
定义一个数组ans
清除数组arr
对于初始化i：=0，当i<k时，更新（将i增加1），执行-
调用函数insert（nums[i]）
对于初始化i：=k，j：=0，当i<nums的大小时，更新（i增加1），（j增加1），-
getMedian()在ans结尾处插入返回值
调用函数delete_（nums[j]）
调用函数insert（nums[i]）
getMedian()在ans结尾处插入返回值
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
multiset <double> arr;
void insert(double x){
arr.insert(x);
}
void delete_(double x){
arr.erase(arr.find(x));
}
double getMedian(){
int n = arr.size();
double a = *next(arr.begin(), n / 2 - 1);
double b = *next(arr.begin(), n / 2);
if(arr.size() & 1)return b;
return (a + b) * 0.5;
}
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector <double> ans;
arr.clear();
for(int i = 0; i < k; i++){
insert(nums[i]);
}
for(int i = k, j = 0; i < nums.size(); i++, j++){
ans.push_back(getMedian());
delete_(nums[j]);
insert(nums[i]);
}
ans.push_back(getMedian());
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,3,-1,-3,5,3,6,8};
print_vector(ob.medianSlidingWindow(v, 3));
}输入项
{1,3,-1,-3,5,3,6,8}输出结果
[1, -1, -1, 3, 5, 6, ]