假设我们有一个数字列表，并且有一个窗口大小k，我们必须使用滑动窗口方式找到中位数列表。因此，如果分布如下所示-
| 窗口位置 | 中位数 | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 1 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | -1 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | -1 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 3 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 5 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 6 | |
这里我们考虑了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, ]