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, ]