algorithm
Schiebefenster-Algorithmus

Schiebefenster-Algorithmus Grundlegende Informationen

Der Schiebefenster-Algorithmus wird verwendet, um die erforderliche Operation für eine bestimmte Fenstergröße eines gegebenen großen Puffers oder Arrays durchzuführen. Das Fenster beginnt mit dem 1. Element und wird um ein Element nach rechts verschoben. Ziel ist es, die in jedem Fenster vorhandenen minimalen k-Zahlen zu finden. Dies wird allgemein als Schiebefensterproblem oder Algorithmus bezeichnet.

Um zum Beispiel das maximale oder minimale Element aus jedem n Element in einem gegebenen Array zu finden, wird ein Schiebefenster-Algorithmus verwendet.

Beispiel:

Eingangsfeld: [1 3 -1 -3 5 3 6 7]

Fenstergröße: 3

Maximales Element von jedem 3 Element des Eingabearrays:

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

Minimales Element von jedem 3 Element des Eingabearrays:

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

Methoden zur Ermittlung der Summe von 3 Elementen:

Methode 1:

Der erste Weg ist die schnelle Sortierung. Wenn sich der Drehpunkt in der K-ten Position befindet, sind alle Elemente auf der rechten Seite größer als der Drehpunkt. Daher werden alle Elemente auf der linken Seite automatisch zu K kleinsten Elementen einer gegebenen Anordnung.

Methode 2:

Behalten Sie ein Array von K Elementen bei, füllen Sie es mit den ersten K Elementen des angegebenen Eingabefeldes. Überprüfen Sie nun bei K + 1-Element, ob das aktuelle Element unter dem maximalen Element im Hilfsarray liegt. Wenn ja, fügen Sie dieses Element dem Array hinzu. Das einzige Problem bei der obigen Lösung ist, dass wir das maximale Element im Auge behalten müssen. Noch funktionsfähig Wie können wir das maximale Element im Integer-Satz verfolgen? Denke über Haufen. Denke über Max Heap.

Methode 3:

Großartig! In O (1) würden wir das max-Element unter den bereits als kleinste K-Elementen ausgewählten K-Elementen erhalten. Wenn max im aktuellen Satz größer als das neu berücksichtigte Element ist, müssen wir max entfernen und ein neues Element in den Satz des kleinsten Elements einführen. Heapify erneut, um die Heap-Eigenschaft zu erhalten. Jetzt können wir leicht K Minimum-Elemente in einem Array von N erhalten.

Weltraumhilfsmittel: O(n)

Zeitkomplexität: O(n)

Implementierung des Sliding Window-Algorithmus 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);
    }
}