Нахождение второго по величине элемента в скользящем окне

Question

Итак, учитывая массив и размер окна, мне нужно найти второе по величине в каждом окне. Решение грубой силы довольно просто, но я хочу найти эффективное решение с использованием динамического программирования

Решение по грубой силе истекает, когда я пробую его для больших массивов, поэтому мне нужно найти лучшее решение. Мое решение состояло в том, чтобы найти второе по величине в каждом скользящем окне, отсортировав их и получив второй элемент, я понимаю, что некоторые структуры данных могут сортироваться быстрее, но я хотел бы знать, есть ли лучшие способы.

Answer 1

Есть много способов решить эту проблему.Вот пара вариантов.В дальнейшем я буду обозначать число элементов n во входном массиве, а w - размер окна.

Вариант 1: простой алгоритм O (n log w) -time

Один из вариантов - сохранить сбалансированное двоичное дерево поиска, содержащее все элементы в текущем окне, включая дубликаты.Для вставки чего-либо в этот BST потребовалось бы время O (log w), поскольку в окне всего w элементов, а удаление элемента также заняло бы время O (log w) по той же причине.Это означает, что скольжение окна на одну позицию занимает время O (log w).

Чтобы найти второй по величине элемент в окне, вам просто нужно применить стандартный алгоритм для поискавторой по величине элемент в BST , который занимает время O (log w) в BST с элементами w.

Преимущество этого подхода состоит в том, что в большинстве языков программирования это будет довольнопросто закодировать это.Это также использует кучу известных стандартных методов.Недостатком является то, что время выполнения не является оптимальным, и мы можем улучшить его.

Вариант 2: Алгоритм префикса / суффикса O (n)

Вот решение с линейным временем, которое относительнопросто реализовать.На высоком уровне решение работает, разбивая массив на ряд блоков, каждый из которых имеет размер w.Например, рассмотрим следующий массив:

31  41  59  26  53  58  97  93  23  84  62  64  33  83  27  95  02  88  41  97

Представьте, что w = 5. Мы разделим массив на блоки размером 5, как показано здесь:

31  41  59  26  53 | 58  97  93  23  84 | 62  64  33  83  27 | 95  02  88  41  97

Теперь,представьте, что в этом массиве нужно разместить окно длиной 5, как показано здесь:

31  41  59  26  53 | 58  97  93  23  84 | 62  64  33  83  27 | 95  02  88  41  97
                             |-----------------|

Обратите внимание, что это окно всегда будет состоять из суффикса одного блока, за которым следует префикс другого.Это хорошо, потому что позволяет нам решить несколько более простую проблему.Представьте, что каким-то образом мы можем эффективно определить два самых больших значения в любом префиксе или суффиксе любого блока.Тогда мы могли бы найти значение second-max в любом окне следующим образом:

• Выяснить, какому префиксу блоков и суффиксу соответствует окно.
• Получить два верхних элемента из каждогоиз этих префиксов и суффиксов (или только одного верхнего элемента, если окно достаточно маленькое).
• Из этих (до) четырех значений определите, какое является вторым по величине, и верните его.

С небольшой предварительной обработкой мы действительно можем настроить наши окна для ответа на запросы вида "каковы два самых больших элемента в каждом суффиксе?"и "каковы два самых больших элемента в каждом префиксе?"Вы можете рассматривать это как проблему динамического программирования, настроенную следующим образом:

• Для любого префикса / суффикса длины один, сохраните одно значение в этом префиксе / суффиксе.
• Для любого префикса / суффикса длины два верхние два значения - это сами два элемента.
• Для любого более длинного префикса или суффикса этот префикс или суффикс можно сформировать, расширив меньший префикс или суффикс наодин элементЧтобы определить два верхних элемента этого более длинного префикса / суффикса, сравните элемент, используемый для расширения диапазона, до двух верхних элементов и выберите два верхних из этого диапазона.

Обратите внимание, что заполнение каждогоДва верхних значения префикса / суффикса занимают время O (1).Это означает, что мы можем заполнить любое окно за время O (w), так как есть w записей для заполнения. Более того, поскольку существует всего O (n / w) окон, общее время, необходимое для заполнения этих записей, составляет O(n), поэтому наш общий алгоритм работает за время O (n).

Что касается использования пространства: если вы с нетерпением вычисляете все значения префикса / суффикса во всем массиве, вам нужно использовать пространство O (п) держать все.Однако, поскольку в любой момент времени мы заботимся только о двух окнах, вы можете альтернативно вычислять префиксы / суффиксы только тогда, когда они вам нужны.Для этого потребуется только пробел O (w), что действительно очень хорошо!

Вариант 3: решение за O (n) время с использованием умных структур данных

Этот последний подход оказывается полностью эквивалентным вышеописанному подходу, но формирует его по-другому.

Можно построить очередь, которая позволяет в постоянное время запрашивать его максимальный элемент . Идея этой очереди - начиная с стека, который поддерживает эффективный find-max , а затем используя его в построении очереди с двумя стеками, - можно легко обобщить для создания очереди, которая дает постоянный доступ к второй по величине элемент. Для этого нужно просто адаптировать конструкцию стека для хранения двух верхних элементов в каждый момент времени, а не только самого большого элемента.

Если у вас есть очередь, подобная этой, алгоритм поиска значения second-max в любом окне довольно быстрый: загрузите очередь с первыми элементами w, а затем несколько раз снимите с очереди элемент (сдвиньте что-нибудь из окна) и поставьте в очередь следующий элемент (сдвиньте что-нибудь в окно). Каждая из этих операций занимает амортизированное O (1) время для завершения, поэтому это занимает время O (n) в целом.

Забавный факт - если вы посмотрите на то, что на самом деле делает эта реализация очереди в данном конкретном случае, вы обнаружите, что она полностью эквивалентна приведенной выше стратегии. Один стек соответствует суффиксам предыдущего блока, а другой - префиксам следующего блока.

Эта последняя стратегия - мой личный фаворит, но по общему признанию, это - только мое собственное смещение структур данных.

Надеюсь, это поможет!

Answer 2

Так что просто возьмите структуру данных как набор, который хранит данные по порядку.например, если вы сохраняете 4 2 6 на множестве, оно будет сохраняться как 2 4 6.

Так, каков будет алгоритм:

Let,

Array = [12,8,10,11,4,5] размер окна = 4

первое окно = [12,8,10,11] set = [8,10,11,12]

Какчтобы получить второе место:
- Удалить последний элемент из набора и сохранить в контейнере.set = [8,10,11], contaniner = 12
- После удаления текущий последний элемент набора является вторым по величине в текущем окне.
- Снова поместите удаленный элемент, хранящийся в контейнере, вset, set = [8,10,11,12]
Теперь сдвиньте окно, - удалите 12 из набора и добавьте 4.
- Теперь вы получите новое окно и установите.
- проверкакак аналогичный процесс.
Сложность удаления и добавления элемента в набор составляет около log (n).

Один прием:

Если вы всегда хотите хранить данные в порядке убывания, затем вы можете сохранить данные, умножив их на -1.И когда вы откроете данные, используйте их, умножив их на -1.

Answer 3

Мы можем использовать двустороннюю очередь для решения O (n). Передняя часть очереди будет иметь более крупные (и ранее замеченные) элементы:

  0  1  2  3  4  5
{12, 8,10,11, 4, 5}
window size: 3

i   queue (stores indexes)
-   -----
0   0
1   1,0
2   2,0 (pop 1, then insert 2)
output 10
remove 0 (remove indexes not in
   the next window from the front of
   the queue.)
3   3 (special case: there's only one
   smaller element in queue, which we
   need so keep 2 as a temporary variable.)
output 10
4   4,3
output 10
remove 2 from temporary storage
5   5,3 (pop 4, insert 5)
output 5

"pop" и "remove from front" равны while A[queue_back] <= A[i] и while queue_front is outside next window соответственно (несмотря на сложность только одного меньшего элемента, оставшегося в очереди). Мы выводим элемент массива, проиндексированный вторым элементом, из передней части очереди (хотя у нашего фронта может быть специальный временный друг, который тоже когда-то был впереди; специальный друг сбрасывается, как только он представляет элемент, находящийся вне окна или меньше, чем элемент, проиндексированный вторым элементом очереди спереди). Двусторонняя очередь имеет сложность O (1), которую нужно удалить спереди или сзади. Вставляем только сзади.

По запросу templatetypedef в комментариях: «Как вы определяете, какие операции очереди использовать?» На каждой итерации с индексом i перед вставкой в ​​очередь мы (1) извлекаем каждый элемент из конца очереди, представляющий элемент в массиве, меньший или равный A[i], и (2) удалить каждый элемент в начале очереди, который является индексом за пределами текущего окна. (Если во время (1) у нас останется только один элемент меньшего или равного размера, мы сохраняем его как временную переменную, поскольку он является вторым по величине на текущий момент.)

Answer 4

Существует относительно простое решение для программирования на основе дунами O(n^2): Создайте классическую структуру пирамиды для совокупного значения по подмножеству (то, где вы объединяете значения из пар ниже, чтобы сделать каждый шаг выше), где вы отслеживаете самые большие 2 значения (и их положение), а затем просто сохраняете самые большие 2 значения из 4 комбинированных значений (которые на практике меньше из-за перекрытия, используйте положение, чтобы убедиться, что они на самом деле разные). Затем вы просто считываете второе по величине значение слоя с правильным размером скользящего окна.