Алгоритм для определения индексов i.. j массива A содержащий все элементы другого массива B
Как упомянуто в https://github.com/angular/angular-cli/issues/9488#issuecomment-368871510 , похоже, он работает с ng serve --aot
2 ответа
Сложность
Время: O ((m + n) log m)
Пространство: O (m)
Следующее доказуемо оптимально с точностью до логарифмического множителя. (Я считаю, что от лог-фактора невозможно избавиться, поэтому он оптимален.)
Вариант 1 - это просто частный случай варианта 2 со всеми кратностями, равными 1, после удаления дубликатов из B. Так что достаточно обработать последний вариант; если вам нужен вариант 1, просто удалите дубликаты за O (m log m) времени. Далее пусть m обозначает количество различных элементов в B. Мы предполагаем m -1 в константе времени.
Для каждого индекса i в A мы найдем наименьший индекс s [i] такой, что A [i..s [i]] содержит B [1..m] , с правильными кратностями. Ключевое наблюдение состоит в том, что s [i] не убывает , и это то, что позволяет нам делать это за амортизированное линейное время.
Начнем с i = j = 1 . Мы сохраним кортеж (c [1], c [2], ... c [m]) количества раз, когда каждый элемент B встречается в текущем окне A [ i..j] . Мы также сохраним набор S индексов (подмножество 1..m ), для которого счетчик является «правильным» (то есть k , для которого c [k] = 1 в варианте 1 или c [k] = <правильное число> в варианте 2).
Итак, для i = 1 , начиная с j = 1 , увеличиваем каждое c [A [j]] (если A [j] был элементом B), проверьте, правильно ли теперь c [A [j]] , и соответственно добавьте или удалите j из S . Остановитесь, когда S будет иметь размер м . Теперь вы нашли с [1] , самое большее за O (n log m) времени. (Есть O (n) j , и каждая операция набора занимала O (log m) времени.)
Теперь для вычисления последовательных s [i] s, сделайте следующее. Увеличить i , уменьшить c [A [i]] , соответственно обновить S и, при необходимости, увеличить j до ] S снова имеет размер м . Это дает вам s [i] для каждого i . В конце сообщите (i, s [i]) , для которого s [i] -i было наименьшим.
Обратите внимание, что хотя кажется, что вы можете выполнять до O (n) шагов (увеличивая j ) для каждого i , второй указатель j перемещается только вправо: поэтому общее количество раз, которое вы можете увеличить j не более n . (Это амортизированный анализ .) Каждый раз, когда вы увеличиваете j , вы можете выполнять операцию набора, которая занимает O (log m) времени, поэтому общее время равно O (n log m) . Требуемое пространство было для хранения кортежа счетчиков, набора элементов B, набора S и некоторого постоянного числа других переменных, так что всего O (m) .
Существует очевидная O (m + n) нижняя граница , потому что вам нужно изучить все элементы. Таким образом, единственный вопрос заключается в том, сможем ли мы доказать, что коэффициент log необходим; Я считаю, что это так.
Вот решение, о котором я подумал (но оно не очень изящное).
Я собираюсь проиллюстрировать это используя пример из вопроса.
Пусть A [1,2,5,11,2,6,8,24,101,17,8] и B [5,2,11,8,17]
Сортировка B. (Итак, B = [2,5,8,11,17]). Этот шаг занимает O (log m).
Выделить массив C размера A. Перебирать элементы A, бинарный поиск его в отсортированном B, если он найден, введите его «index in sorted B + 1» в C. Если он не найден, введите -1. После этого шага
A = [1, 2, 5, 11, 2, 6, 8, 24, 101, 17, 8] (без изменений, цитируем для удобства).
C = [-1, 1, 2, 4, 1, -1, 3, -1, -1, 5, 3]
Время: (n log m), Пробел O (n).
- Найдите наименьшее окно в C, в котором есть все числа от 1 до m. Чтобы найти окно, я могу думать о двух основных направлениях: а. Бит-ориентированный подход, в котором я устанавливаю бит, соответствующий каждой позиции, и, наконец, проверяю с помощью какого-то И. б. Создайте еще один массив D размера m, пройдите через C и, когда я встречу p в C, увеличьте D [p]. Используйте это для поиска окна.
Пожалуйста, оставьте комментарии относительно общего подхода как такового, а также для 3a и 3b.