algorithm
슬라이딩 윈도우 알고리즘
수색…
슬라이딩 윈도우 알고리즘 기본 정보
슬라이딩 윈도우 알고리즘은 주어진 대형 버퍼 또는 어레이의 특정 창 크기에 대해 필요한 작업을 수행하는 데 사용됩니다. 창은 첫 번째 요소에서 시작하여 한 요소 씩 바로 이동합니다. 목적은 각 창에있는 최소 k 개의 숫자를 찾는 것입니다. 이것은 일반적으로 슬라이딩 윈도우 문제 또는 알고리즘으로 알려져 있습니다.
예를 들어 주어진 배열의 모든 n
요소에서 최대 또는 최소 요소를 찾으려면 슬라이딩 윈도우 알고리즘이 사용됩니다.
예:
입력 배열 : [1 3 -1 -3 5 3 6 7]
창 크기 : 3
입력 배열의 3 요소마다 최대 요소 :
+---------------------------------+---------+
| 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 |
+---+---+----+----+---+-----------+---------+
입력 배열의 3 요소마다 최소 요소 :
+---------------------------------+---------+
| 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 |
+---+---+----+----+---+-----------+---------+
3 요소의 합계를 찾는 방법 :
방법 1 :
첫 번째 방법은 빠른 정렬을 사용하는 것입니다. 피벗이 K 번째 위치에 있으면 오른쪽에있는 모든 요소가 피벗보다 크기 때문에 왼쪽에있는 모든 요소가 자동으로 지정된 배열의 K 개의 가장 작은 요소가됩니다.
방법 2 :
K 요소의 배열 유지, 주어진 입력 배열의 첫 번째 K 요소로 채 웁니다. 이제 K + 1 요소에서 현재 요소가 보조 배열의 최대 요소보다 작은 지 확인하십시오. 그렇다면이 요소를 배열에 추가하십시오. 위의 솔루션의 문제는 최대 요소를 추적해야한다는 것입니다. 아직도 실행할 수 있습니다. 정수 집합에서 최대 원소를 어떻게 추적 할 수 있습니까? 생각 해봐. 최대 힙을 생각하십시오.
방법 3 :
큰! O (1)에서 우리는 가장 작은 K 요소로 이미 선택된 K 요소 중에서 최대 요소를 얻습니다. 현재 설정된 최대 값이 새로 고려 된 요소보다 큰 경우, max를 제거하고 K 가장 작은 요소의 집합에서 새로운 요소를 도입해야합니다. 힙 속성을 유지하려면 다시 Heapify하십시오. 이제 N의 배열에 K 개의 최소 요소를 쉽게 얻을 수 있습니다.
우주 보조 장치 : O(n)
시간 복잡성 : O(n)
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);
}
}