algorithm
Алгоритм раздвижного окна
Поиск…
Алгоритм скользящего окна Основная информация
Алгоритм скользящего окна используется для выполнения требуемой операции для конкретного размера окна заданного большого буфера или массива. Окно начинается с 1-го элемента и смещается справа на один элемент. Цель состоит в том, чтобы найти минимальные 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:
Первый способ - использовать быструю сортировку, когда точка поворота находится в позиции Kth, все элементы с правой стороны больше, чем точка поворота, поэтому все элементы с левой стороны автоматически становятся K наименьшими элементами заданного массива.
Способ 2:
Храните массив элементов K, заполните его с помощью первых элементов K данного массива ввода. Теперь из элемента K + 1 проверьте, является ли текущий элемент меньше максимального элемента во вспомогательном массиве, если да, добавьте этот элемент в массив. Единственная проблема с вышеупомянутым решением заключается в том, что нам нужно отслеживать максимальный элемент. Все еще работоспособно. Как мы можем отслеживать максимальный элемент в наборе integer? Подумайте, куча. Подумайте, Макс куча.
Способ 3:
Большой! В O (1) мы получили бы максимальный элемент среди K элементов, которые были выбраны как самые маленькие K-элементы. Если max в текущем наборе больше, чем новый элемент, нам нужно удалить max и ввести новый элемент в множество наименьшего элемента K. Heapify снова, чтобы сохранить свойство кучи. Теперь мы можем легко получить K минимальных элементов в массиве N.
Вспомогательный объем: 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);
}
}