算法设计（数组中滑动窗口的中位数|S2） _数据结构

本文概述

先决条件：基于策略的数据结构, 滑窗技术.
给定一个整数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的窗口，对窗口的元素进行排序，并找到中间的元素。打印每个窗口的中间元素作为中间值。
【算法设计（数组中滑动窗口的中位数|S2）】时间复杂度：O(N * KlogK)
辅助空间：O(K)
排序集方法：参考数组中滑动窗口的中位数解决问题SortedSet.
有序集方法：
在本文中，一种使用基于策略的有序集数据结构来解决这个问题的方法。
请按照以下步骤解决问题：

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

下面是上述方法的实现。
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; }

输出如下：