algorithm
Skjutfönsteralgoritm

Grundläggande information för glidfönsteralgoritm

Skjutfönsteralgoritmen används för att utföra erforderlig operation på specifik fönsterstorlek för en given stor buffert eller array. Fönstret startar från det första elementet och fortsätter att skifta åt höger med ett element. Målet är att hitta de minsta k-numren som finns i varje fönster. Detta är vanligtvis känt som glidfönsterproblem eller algoritm.

Till exempel för att hitta det maximala eller minsta elementet från varje n element i en given array används skjutfönsteralgoritmen.

Exempel:

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

Fönsterstorlek: 3

Maximalt element från varje 3-element inmatningsfält:

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

Minsta element från varje 3-element inmatningsfält:

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

Metoder för att hitta summan av 3 element:

Metod 1:

Det första sättet är att använda snabbsortering, när pivot är i Kth-position är alla element på höger sida större än pivot, alltså blir alla element på vänster sida automatiskt K minsta element i en given grupp.

Metod 2:

Behåll en matris med K-element, fyll den med första K-element i en given matris. Kontrollera nu från K + 1-elementet om det aktuella elementet är mindre än det maximala elementet i hjälpfältet, om ja, lägg till detta element i arrayen. Det enda problemet med lösningen ovan är att vi måste hålla reda på maximalt element. Fortfarande fungerande. Hur kan vi hålla reda på maximalt element i uppsättning heltal? Tänk hög. Tror Max hög.

Metod 3:

Bra! I O (1) skulle vi få maxelementet bland K-element som redan valts som minsta K-element. Om max i den aktuella uppsättningen är större än nyligen betraktade element, måste vi ta bort max och införa nytt element i uppsättningen av K minsta element. Heapify igen för att upprätthålla heap-fastigheten. Nu kan vi enkelt få K-minimumelement i matris av N.

Space Auxiliary: O(n)

Tidskomplexitet: O(n)

Implementering av glidfönsteralgoritmen i 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);
    }
}