Ближайшие равные числа

Назовите интервал минимальным, если его первое число равно последнему, но каждое из чисел между ними встречается ровно один раз в интервале. 11 и 101 минимальны, а 12021 и 10101 нет.

В линейном времени (при условии хэширования с постоянным временем) перечислите все минимальные интервалы. Это можно сделать, сохранив два индекса, l и k, и хеш-карту, которая сопоставляет каждый символ между l и k с его индексом. Изначально l = 1 и k = 0. Неоднократно проделайте следующее. Увеличиваем k (если слишком большое, останавливаемся). Если символ с новым значением k есть на карте, то продвиньте l к значению карты, удаляя все с карты по мере продвижения. Получите интервал [l, k] и еще раз увеличьте l. Во всех случаях пишите k в качестве значения карты символа.

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

Мы можем сделать это в O(nlog(n)) с сортировкой. Во-первых, пометьте все элементы в [l,k] их первоначальными индексами. Затем отсортируйте элементы в [l,k], сначала по значению, а затем по исходному индексу, оба по возрастанию.

Затем вы можете просмотреть отсортированный список, сохраняя переменную currentValue и проверяя соседние значения, которые одинаковы для расстояния, и при необходимости устанавливая minDistance. currentValue обновляется, когда вы достигаете нового значения в отсортированном списке.

Предположим, у нас есть этот диапазон [l,k] из вашего второго примера:

1 2 3 0 3 2 3

Мы можем пометить их как

1(1) 2(2) 3(3) 0(4) 3(5) 2(6) 3(7)

и отсортировать их как

0(4) 1(1) 2(2) 2(6) 3(3) 3(5) 3(7)

Зациклив это, нет диапазонов для 0 и 1. Минимальное расстояние для 2s равно 4, а минимальное расстояние для 3s равно 2 ([3,5] или [3,7], в зависимости от того, сбросили ли вы minDistance, когда новое минимальное расстояние равно текущему минимальному расстоянию).

Таким образом, мы получаем

[3,5] in [l,k] or [5,7] in [l,k]

ИЗМЕНИТЬ

Поскольку вы упомянули некоторые запросы, вы можете предварительно обработать список за O(nlog(n)) времени, а затем использовать только O(n) времени для каждого отдельного запроса. Вы бы просто проигнорировали индексы, которых нет в [l,k], при циклическом просмотре отсортированного списка.

ИЗМЕНИТЬ 2

Это относится к разъяснению вопроса, в котором теперь говорится, что всегда будет много запросов для выполнения. Мы можем выполнить предварительную обработку за O(n^2) времени с помощью динамического программирования, а затем выполнить каждый запрос за O(1) времени.

Сначала выполните препроцессинг всего списка, который я описал выше. Затем через O(n) времени сформируйте ссылки из исходного списка в отсортированный список.

Мы можем представить, что:

[l,k] = min([l+1,k], [l,k-1], /*some other sequence starting at l or ending at k*/)

У нас есть один базовый случай

[l,k] = infinity where l = k

Если [l,k] не min([l+1,k], [l,k-1]), то оно либо начинается с l, либо заканчивается с k. Мы можем взять каждый из них, просмотреть отсортированный список и посмотреть на соседний элемент в правильном направлении и проверить расстояния (убедившись, что мы в границах). Нам нужно проверить только 2 элемента, так что это постоянный коэффициент.

Используя этот алгоритм, мы можем запустить следующее

for l = n downto 1
    for k = l to n
        M[l,k] = min(M[l+1,k], M[l,k-1], sequence starting at l, sequence ending at k)

Вы также можете хранить решения в матрице (которая на самом деле является пирамидой). Затем, когда вам дается запрос [l,k], вы просто ищете его в матрице.