algorithm
Algoritmo per finestra scorrevole

Algoritmo della finestra scorrevole Informazioni di base

L'algoritmo della finestra scorrevole viene utilizzato per eseguire l'operazione richiesta su dimensioni specifiche della finestra di un determinato buffer o array di grandi dimensioni. La finestra parte dal primo elemento e continua a spostarsi a destra di un elemento. L'obiettivo è trovare i numeri k minimi presenti in ogni finestra. Questo è comunemente noto come problema o algoritmo della finestra scorrevole.

Ad esempio, per trovare l'elemento massimo o minimo da ogni elemento n in un determinato array, viene utilizzato l'algoritmo della finestra scorrevole.

Esempio:

Input Array: [1 3 -1 -3 5 3 6 7]

Dimensione della finestra: 3

Elemento massimo da ogni 3 elementi dell'array di input:

+---------------------------------+---------+
|      Windows Position           |   Max   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |    3    |
+------------+----+---+---+---+---+---------+
| 1 |[3   -1   -3]| 5 | 3 | 6 | 7 |    3    |
+---+-------------+---+---+---+---+---------+
| 1 | 3 |[-1   -3   5]| 3 | 6 | 7 |    5    |
+---+---+-------------+---+---+---+---------+
| 1 | 3 | -1 |[-3   5   3]| 6 | 7 |    5    |
+---+---+----+------------+---+---+---------+
| 1 | 3 | -1 | -3 |[5   3   6]| 7 |    6    |
+---+---+----+----+-----------+---+---------+
| 1 | 3 | -1 | -3 | 5 |[3   6   7]|    7    |
+---+---+----+----+---+-----------+---------+

Elemento minimo da ogni 3 elementi dell'array di input:

+---------------------------------+---------+
|      Windows Position           |   Min   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |   -1    |
+------------+----+---+---+---+---+---------+
| 1 |[3   -1   -3]| 5 | 3 | 6 | 7 |   -3    |
+---+-------------+---+---+---+---+---------+
| 1 | 3 |[-1   -3   5]| 3 | 6 | 7 |   -3    |
+---+---+-------------+---+---+---+---------+
| 1 | 3 | -1 |[-3   5   3]| 6 | 7 |   -3    |
+---+---+----+------------+---+---+---------+
| 1 | 3 | -1 | -3 |[5   3   6]| 7 |    3    |
+---+---+----+----+-----------+---+---------+
| 1 | 3 | -1 | -3 | 5 |[3   6   7]|    3    |
+---+---+----+----+---+-----------+---------+

Metodi per trovare la somma di 3 elementi:

Metodo 1:

Il primo modo è usare l'ordinamento rapido, quando il pivot è in posizione Kth, tutti gli elementi sul lato destro sono maggiori di pivot, quindi, tutti gli elementi sul lato sinistro diventano automaticamente K gli elementi più piccoli di un determinato array.

Metodo 2:

Mantieni un array di elementi K, riempilo con i primi elementi K di un determinato array di input. Ora dall'elemento K + 1, controlla se l'elemento corrente è inferiore all'elemento massimo nell'array ausiliario, se sì, aggiungi questo elemento all'array. L'unico problema con la soluzione di cui sopra è che dobbiamo tenere traccia dell'elemento massimo. Ancora praticabile Come possiamo tenere traccia dell'elemento massimo in un insieme di numeri interi? Pensa al mucchio. Pensa al mucchio di Max.

Metodo 3:

Grande! In O (1) otterremmo il massimo elemento tra gli elementi K già scelti come elementi K più piccoli. Se max nel set corrente è maggiore dell'elemento appena considerato, dobbiamo rimuovere max e introdurre un nuovo elemento nel set di K l'elemento più piccolo. Heapify di nuovo per mantenere la proprietà heap. Ora possiamo facilmente ottenere elementi minimi di K nella matrice di N.

Spazio ausiliario: O(n)

Complessità del tempo: O(n)

Implementazione dell'algoritmo della finestra scorrevole in C #

public class SlidingWindow
{
    public static int[] MaxSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var max = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] > max) max = input[i + j];
            }
            result[i] = max;
        }
        return result;
    }

    public static int[] MinSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var min = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] < min) min = input[i + j];
            }
            result[i] = min;
        }
        return result;
    }

    public static int[] MainMax(int[] input, int n)
    {
        return MaxSlidingWindow(input, n);
    }

    public static int[] MainMin(int[] input, int n)
    {
        return MinSlidingWindow(input, n);
    }
}