Мое решение:
а. Создайте хэш-таблицу с m ключами, по одному для каждого значения в B. Каждый ключ в H отображается в динамический массив отсортированных индексов, содержащих индексы в A, равные B [i]. Это занимает O (N) время. Мы просматриваем каждый индекс j в A. Если ключ A [i] существует в H (O (1) время), то добавляем значение, содержащее индекс j of A, в список индексов, в которые отображается H [A [i]] .
На данный момент мы «сгруппировали» n элементов в m корзин. Тем не менее, общий объем памяти просто O (n).
б. Вторая часть алгоритма включает в себя поддержание «левого» и «правого» индекса для каждого списка в H. Давайте создадим два массива размера m, называемых L и R, которые содержат эти значения. Изначально в нашем примере
Мы также отслеживаем «лучшее» минимальное окно.
Затем мы повторяем следующие действия на L и R, которые по своей природе жадные:
я. На каждой итерации мы вычисляем минимальное и максимальное значения в L и R.
Для L, Lmax - Lmin - окно, а для R, Rmax - Rmin - окно. Мы обновляем лучшее окно, если одно из этих окон лучше текущего лучшего окна. Мы используем минимальную кучу, чтобы отслеживать минимальный элемент в L, и максимальную кучу, чтобы отслеживать самый большой элемент в R. Для сборки требуется O (m * log (m)).
II. С «жадной» точки зрения, мы хотим предпринять действие, которое минимизирует размер окна в каждом L и R. Для L это интуитивно имеет смысл увеличить минимальный индекс, а для R имеет смысл уменьшить максимальный индекс.
Мы хотим увеличивать позицию массива для минимального значения, пока он не станет больше, чем 2-й наименьший элемент в L, и аналогичным образом мы хотим уменьшить позицию массива для наибольшего значения в R, пока он не станет меньше, чем 2-й по величине элемент в R.
Далее сделаем ключевое наблюдение:
Если L [i] является минимальным значением в L, а R [i] меньше 2-го наименьшего элемента в L, т. Е. Если R [i] все еще будет минимальным значением в L, если L [i] были заменены на R [i], тогда мы сделали. Теперь у нас есть «лучший» индекс в списке i, который может внести вклад в минимальное окно. Кроме того, все другие элементы в R не могут вносить вклад в лучшее окно, так как все их значения L больше, чем L [i]. Точно так же, если R [j] является максимальным элементом в R, а L [j] больше 2-го по величине значения в R, мы также делаем это путем установки R [j] = L [j]. Любой другой индекс в массиве i слева от L [j] уже учтен, как и все индексы справа от R [j], и все индексы между L [j] и R [j] будут работать хуже, чем L [J].
В противном случае мы просто увеличиваем позицию массива L [i] до тех пор, пока она не станет больше 2-го наименьшего элемента в L, и уменьшаем позицию массива R [j] (где R [j] - максимум в R), пока она не станет меньше чем второй по величине элемент в R. Мы вычисляем окна и обновляем лучшее окно, если одно из окон L или R меньше лучшего окна. Мы можем выполнить поиск Фибоначчи, чтобы оптимально сделать приращение / уменьшение. Мы продолжаем увеличивать L [i], используя приращения Фибоначчи, пока не будем больше, чем 2-й по величине элемент в L. Затем мы можем выполнить бинарный поиск, чтобы получить наименьший элемент L [i], который больше, чем 2-й по величине элемент в L, аналогично для набор R. После увеличения / уменьшения мы извлекаем самый большой элемент из максимальной кучи для R и минимальный элемент для минимальной кучи для L и вставляем новые значения L [i] и R [j] в кучи. Это операция O (log (m)).
Шаг ii. завершится, когда Lmin не сможет больше двигаться вправо или Rmax не сможет больше двигаться влево (так как значения R / L одинаковы). Обратите внимание, что у нас могут быть сценарии, в которых L [i] = R [i], но если это не минимальный элемент в L или максимальный элемент в R, алгоритм все равно будет продолжаться.
Анализ времени выполнения:
а. Создание хеш-таблицы занимает O (n) времени и O (n) пространства.
б. Создание куч: O (m * log (m)) время и O (m) пространство.
с. Жадный итеративныйалгоритм немного сложнее анализировать. Его время выполнения действительно ограничено распределением элементов. В худшем случае мы покрываем все элементы каждого массива в хэш-таблице. Для каждого элемента мы выполняем обновление кучи O (log (m)).
Время выполнения в худшем случае, следовательно, O (n * log (m)) для итеративного жадного алгоритма. В лучшем случае мы очень быстро обнаружим, что L [i] = R [i] для минимального элемента в L или максимального элемента в R… время выполнения O (1) * log (m) для жадного алгоритма!
Средний случай кажется действительно сложным для анализа. Какова средняя «сходимость» этого алгоритма к минимальному окну. Если бы мы предположили, что инкременты Фибоначчи / бинарный поиск должны были помочь, мы могли бы сказать, что мы рассматриваем только элементы m * log (n / m) (каждый список имеет n / m элементов) в среднем случае. В этом случае время работы алгоритма жадности будет m * log (n / m) * log (m).
Общее время работы
Наилучший случай: O (n + m * log (m) + log (m)) время = O (n) в предположении, что m << n
Средний случай: O (n + m * log (m) + m * log (n / m) * log (m)) время = O (n) в предположении, что m << n.
В худшем случае: O (n + n * log (m) + m * log (m)) = O (n * log (m)) в предположении m << n. </p>
Пробел: O (n + m) (хеш-таблица и куча) всегда.
Редактировать: Вот отработанный пример:
A [5, 1, 1, 5, 6, 1, 1, 5]
Б [5, 6]
H:
{
5 => {1, 4, 8}
6 => {5}
}
Жадный алгоритм:
L => {1, 1}
R => {3, 1}
Итерация 1:
а. Lmin = 1 (так как H {5} [1]
L => {2, 1}
Rmin = H {6} [1] = 5, Rmax = H {5} [3] = 8. Окно = 8 - 5 + 1 = 4. Лучшее окно на данный момент = 4 (меньше 5, вычисленное выше) ,
Также отметим индексы в A (5, 8) для лучшего окна.
Уменьшите Rmax, теперь оно становится равным 2, а значение равно 4.
R => {2, 1}
б. Теперь Lmin = 4 (H {5} [2]), индекс i в L равен 1. Lmax = 5 (H {6} [1]), а индекс в L равен 2.
Мы не можем увеличивать Lmin, так как L [1] = R [1] = 2. Таким образом, мы сейчас просто вычисляем окно.
Окно = Lmax - Lmin + 1 = 2, которое является лучшим окном на данный момент.
Таким образом, лучшее окно в A = (4, 5).