algorithm
Schuifraam algoritme

Schuifvenster-algoritme Basisinformatie

Schuifraam-algoritme wordt gebruikt om de vereiste bewerking uit te voeren op een specifieke venstergrootte van een gegeven grote buffer of array. Het venster begint bij het eerste element en blijft telkens één element naar rechts schuiven. Het doel is om in elk venster de minimale k-nummers te vinden. Dit wordt meestal een schuifraamprobleem of algoritme genoemd.

Om bijvoorbeeld het maximale of minimale element van elk n element in een gegeven array te vinden, wordt een schuifraamalgoritme gebruikt.

Voorbeeld:

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

Venstergrootte: 3

Maximaal element van elk 3 elementen van invoerarray:

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

Minimaal element van elk 3 elementen van invoerarray:

+---------------------------------+---------+
|      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 om de som van 3 elementen te vinden:

Methode 1:

De eerste manier is om snel sorteren te gebruiken, wanneer het draaipunt zich in de Kth-positie bevindt, zijn alle elementen aan de rechterkant groter dan het draaipunt, vandaar dat alle elementen aan de linkerkant automatisch K kleinste elementen van een gegeven array worden.

Methode 2:

Houd een array van K-elementen, vul deze met de eerste K-elementen van de gegeven invoerarray. Controleer nu vanuit het K + 1-element of het huidige element kleiner is dan het maximale element in de hulparray, voeg zo ja dit element toe aan de array. Het enige probleem met bovenstaande oplossing is dat we het maximale element moeten bijhouden. Nog steeds werkbaar. Hoe kunnen we het maximale element in een geheel getal bijhouden? Denk hoop. Denk aan Max.

Methode 3:

Super goed! In O (1) zouden we het max-element krijgen van de K-elementen die al als kleinste K-elementen zijn gekozen. Als max in huidige set groter is dan nieuw beschouwd element, moeten we max verwijderen en nieuw element in set van K smallest element introduceren. Heapify opnieuw om de heap-eigenschap te behouden. Nu kunnen we eenvoudig K-minimumelementen krijgen in een reeks van N.

Extra ruimte: O(n)

Tijd Complexiteit: O(n)

Implementatie van schuifraamalgoritme 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);
    }
}