Mediana de ventana deslizante en una array | conjunto 2

Requisitos previos: estructura de datos basada en políticas , técnica de ventana deslizante .
Dada una array de enteros arr[] y un entero K , la tarea es encontrar la mediana de cada ventana de tamaño K comenzando desde la izquierda y moviéndose hacia la derecha una posición cada vez.
Ejemplos: 
 

Entrada: arr[] = {-1, 5, 13, 8, 2, 3, 3, 1}, K = 3 Salida 
: 5 8 8 3 3 3 
Explicación: 
1ra ventana: {-1, 5, 13} Mediana = 5 
2.ª ventana: {5, 13, 8} Mediana = 8 
3.ª ventana: {13, 8, 2} Mediana = 8 
4.ª ventana: {8, 2, 3} Mediana = 3 
5.ª ventana: {2, 3, 3 } Mediana = 3 
Sexta ventana: {3, 3, 1} Mediana = 3
Entrada: arr[] = {-1, 5, 13, 8, 2, 3, 3, 1}, K = 4 
Salida: 6,5 6,5 5,5 3,0 2,5 
 

Enfoque ingenuo: 
el enfoque más simple para resolver el problema es atravesar cada ventana de tamaño K y ordenar los elementos de la ventana y encontrar el elemento central. Imprime el elemento central de cada ventana como la mediana. 
Complejidad de tiempo: O(N*KlogK) 
Espacio auxiliar: O(K)
Enfoque de conjunto ordenado: consulte la mediana de la ventana deslizante en una array para resolver el problema usando SortedSet .
Enfoque de conjunto ordenado: 
en este artículo, un enfoque para resolver el problema utilizando una estructura de datos de conjunto ordenado basada en políticas . 
Siga los pasos a continuación para resolver el problema: 
 

1. Inserte la primera ventana de tamaño K en Ordered_set (mantiene un orden ordenado). Por lo tanto, el elemento medio de este Conjunto ordenado es la mediana requerida de la ventana correspondiente. 
    
2. El elemento intermedio se puede obtener mediante el método find_by_order() en complejidad computacional O(logN) .
3. Continúe con las siguientes ventanas eliminando el primer elemento de la ventana anterior e insertando el nuevo elemento. Para eliminar cualquier elemento del conjunto, encuentre el orden del elemento en Ordered_Set usando order_by_key() , que obtiene el resultado en complejidad computacional O(logN), y borre() ese elemento buscando su orden obtenido en Ordered_Set usando find_by_order() método. Ahora agregue el nuevo elemento para la nueva ventana. 
    
4. Repita los pasos anteriores para cada ventana e imprima las respectivas medianas. 
    

A continuación se muestra la implementación del enfoque anterior.
 

// 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

Complejidad temporal: O(NlogK) 
Espacio auxiliar: O(K)