как найти n-й минимум / максимум из всех подмассивов размера k (проблема скользящего окна)

#arrays #algorithm #data-structures

#массивы #алгоритм #структуры данных

Вопрос:

Существует так много ссылок, чтобы найти минимум / максимум из всех подмассивов размера k, но как найти n-й максимум / минимум наилучшим возможным способом. Если нам нужно найти только минимальное / максимальное количество подмассивов, то мы можем использовать решение deque с линейной временной сложностью. Но для n-го минимума / максимума я не могу найти решение.

Примечание: n<=k

Пример: arr = {7,1,4,20,11,17,15} n = 2, k = 4

вывод: 4,4,11,15

1. Вопросы должны быть самодостаточными. Каков ваш подход?

2. Что вы подразумеваете под «лучше»? Детерминированное линейное время? Меньший постоянный коэффициент?

3. @user202729 Я упомянул о своем подходе. Должен ли я уточнить больше?

4. @user202729 Просто хочу знать, каков наилучший подход к этой проблеме. Например, могу ли я изменить решение проблемы со скользящим окном, используя deque, и все будет сделано. Я имею в виду, сможем ли мы решить это за линейное время.

5. Пожалуйста, предоставьте любую необходимую информацию из связанных статей в тексте вопроса. Ссылки могут обрываться. (Это также может помочь нам всем упорядочить наши мысли вокруг того, что важно для этого вопроса.)

Ответ №1:

Я полагаю, что нужная вам структура данных — это немного модифицированное двоичное дерево поиска (BST), где каждый узел также хранит размер своего поддерева.

Добавление, удаление элементов или нахождение n-го элемента в BST все тогда становится log(K) * . Таким образом, при перемещении окна по вашему массиву у вас есть 3 log(K) операции, предполагающие общее количество N элементов в данном массиве, следовательно, общая временная сложность N*log(K) .

Вам нужен сбалансированный BST (например, красно-черное дерево), чтобы поддерживать эту временную сложность. Если вы обращаетесь к каким-либо онлайн-судьям, таким как Codeforce или Hackerrank, помните, что они чаще всего предоставляют входные данные, которые будут генерировать вырожденные BSTS.