C++ 中的滑动窗口中位数

假设我们有一列数字，并且有一个窗口大小 k，我们需要使用滑动窗口的方式找到中位数列表。因此，如果分布如下所示：

窗口位置中位数
13-1-353681
13-1-35368-1
13-1-35368-1
13-1-353683
13-1-353685
13-1-353686

这里我们假设 k 为 3，结果将是 [1,-1,-1,3,5,6]

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个集合 arr
  • 定义一个函数 insert()，它将接收 x，
  • 将 x 插入到 arr 中
  • 定义一个函数 delete_()，它将接收 x，
  • 从 arr 中删除 x，如果存在
  • 定义一个函数 getMedian()
  • n := arr 的大小
  • a := 从 arr 的第一个元素开始向前跳跃 n/2 – 1 步，并获取其值
  • 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, ]

更新于: 2020年6月1日

1K+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告