算法设计：数组中滑动窗口的中位数|S2

本文概述

• CPP

先决条件： 基于策略的数据结构, 滑窗技术.

给定一个整数arr[]和整数K的数组，任务是找到每个大小为K的窗口的中值，从左开始，每次向右移动一个位置。

例子：

输入：arr[] = {-1, 5, 13, 8, 2, 3, 3, 1}, K = 3
输出：5 8 8 3 3 3
说明：
第一个窗口：{-1, 5, 13}中值= 5
第二窗口：{5, 13, 8}中位数= 8
第三窗口：{13, 8, 2}中位数= 8
第四窗口：{8, 2, 3}中位数= 3
第五窗口：{2, 3, 3 }中位数= 3
第六个窗口：{3, 3, 1}中位数= 3
输入：arr[] = {-1、5、13、8、2、3、3、1}, K = 4
输出：6.5 6.5 5.5 3.0 2.5

简单的方法：

解决这个问题最简单的方法是遍历每个大小为K的窗口，对窗口的元素进行排序，并找到中间的元素。打印每个窗口的中间元素作为中间值。

时间复杂度：O(N * KlogK)

辅助空间：O(K)

排序集方法：参考数组中滑动窗口的中位数解决问题SortedSet.

有序集方法：

在本文中，一种使用基于策略的有序集数据结构来解决这个问题的方法。

请按照以下步骤解决问题：

1. 插入第一个窗口大小ķ在Ordered_set中(维护排序顺序)。因此, 此有序集合的中间元素是相应窗口的所需中间值。
2. 中间元素可以通过以下方法中的find_by_order()方法获得：O(logN)计算复杂度。
3. 通过删除上一个窗口的第一个元素并插入新元素, 进入以下窗口。要从集合中删除任何元素, 请在Ordered_Set使用order_by_key(), 以O(logN)的计算复杂度获取结果, 并且擦除()通过使用以下命令在Ordered_Set中搜索其获得的顺序来查找该元素find_by_order()方法。现在, 为新窗口添加新元素。
4. 对每个窗口重复上述步骤, 并打印相应的中位数。

下面是上述方法的实现。

CPP

//C++ Program to implement the
//above approach
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
  
using namespace std;
using namespace __gnu_pbds;
  
//Policy based data structure
typedef tree<int , null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
     Ordered_set;
  
//Function to find and return the
//median of every window of size k
void findMedian( int arr[], int n, int k)
{
  
     Ordered_set s;
  
     for ( int i = 0; i <k; i++)
         s.insert(arr[i]);
  
     if (k & 1) {
  
         //Value at index k/2
         //in sorted list.
         int ans = *s.find_by_order(k /2);
  
         cout <<ans <<" " ;
  
         for ( int i = 0; i <n - k; i++) {
  
             //Erasing Element out of window.
             s.erase(s.find_by_order(
                 s.order_of_key(
                     arr[i])));
  
             //Inserting newer element
             //to the window
             s.insert(arr[i + k]);
  
             //Value at index k/2 in
             //sorted list.
             ans = *s.find_by_order(k /2);
  
             cout <<ans <<" " ;
         }
         cout <<endl;
     }
     else {
  
         //Getting the two middle
         //median of sorted list.
         float ans = (( float )*s.find_by_order(
                          (k + 1) /2 - 1)
                      + ( float )*s.find_by_order(k
                                                /2))
                     /2;
  
         printf ( "%.2f " , ans);
  
         for ( int i = 0; i <n - k; i++) {
             s.erase(s.find_by_order(
                 s.order_of_key(arr[i])));
  
             s.insert(arr[i + k]);
  
             ans = (( float )*s.find_by_order(
                        (k + 1) /2 - 1)
                    + ( float )*s.find_by_order(k
                                              /2))
                   /2;
  
             printf ( "%.2f " , ans);
         }
         cout <<endl;
     }
}
  
//Driver Code
int main()
{
     int arr[] = { -1, 5, 13, 8, 2, 3, 3, 1 };
     int k = 3;
  
     int n = sizeof (arr)
             /sizeof (arr[0]);
     findMedian(arr, n, k);
  
     return 0;
}

输出如下：

5 8 8 3 3 3

时间复杂度：O(NlogK)

辅助空间：O(K)

---