Союз перевернутых списков
Дайте k отсортированных инвертированных списков, я хочу эффективный алгоритм, чтобы получить объединение этих k списков? Каждый инвертированный список является массивом только для чтения в памяти, каждый список содержит целое число в отсортированном порядке. результат будет сохранен в предопределенном массиве, который достаточно велик. Есть ли алгоритм лучше, чем k-way merge?
2 ответа
K-Way слияние оптимально. Она имеет O(log(k)*n) опс [где n количество элементов во всех списках вместе взятых.
Легко видеть, что это не может быть сделано лучше - как упомянул @jpalecek, иначе вы могли бы отсортировать любой массив лучше, чем O(nlogn) разделив его на куски [перевернутые индексы] размера 1.
- Примечание. Этот ответ предполагает, что важно, чтобы инвертированные индексы [результирующий массив] были отсортированы. Это предположение верно для большинства приложений, которые используют инвертированные индексы, особенно в области поиска информации. Эта функция [отсортированные индексы] позволяет элегантно и быстро пересекать индексы.
- Примечание: это стандартное k-way merge допускает дублирование, вам нужно убедиться, что если элемент появляется в двух списках, он будет добавлен только один раз [это легко сделать, просто проверив последний элемент в целевом массиве перед добавлением ].
Если вам не нужно сортировать полученный массив, лучшим подходом будет использование хеш-таблицы, чтобы отметить, какой из элементов вы видели. Таким образом, вы можете получить O(n) (n общее количество элементов) сложность времени.
Что-то вроде (Perl):
my %seen;
@merged = grep { exists $seen{$_} ? 0 : ($seen{$_} = 1) } (map {(@$_)} @inputs);