Объединение перевернутых списков

Question

Дайте k отсортированным перевернутым спискам, я хочу, чтобы эффективный алгоритм получил объединение этих k-списков? Каждый перевернутый список является массивом только для чтения в памяти, каждый список содержит целое число в отсортированном порядке. результат будет сохранен в предопределенном массиве, который достаточно велик. Есть ли какой-либо алгоритм лучше, чем слияние k-way?

Answer 1

K-Way слияние оптимально. Он имеет O(log(k)*n) ops [где n - количество элементов во всех списках, объединенных].

Легко видеть, что это не может быть сделано лучше, - как уже упоминалось @jpalecek, в противном случае вы можете сортировать любой массив лучше тогда O(nlogn) путем разделения его на куски [перевернутые индексы] размера 1.

• Примечание: Этот ответ предполагает, что важно, чтобы инвертированные индексы [результирующий массив] будут отсортированы. Это предположение верно для большинства приложений , в которых используются инвертированные индексы, особенно в области информации-поиска . Эта функция [отсортированные индексы] позволяет элегантное и быстрое пересечение индексов.
• Примечание: стандартное слияние k-way позволяет дублировать, вам нужно будет убедиться, что если элемент отображается в двух списках, он будет добавлен только один раз [легко сделать это, просто проверив последний элемент в целевой массив перед добавлением].

Answer 2

Если вам не нужен результирующий массив для сортировки, лучшим подходом будет использование хеш-таблицы, чтобы отметить, какой из элементов вы видели. Таким образом, вы можете получить O(n) (n - общее количество элементов).

Что-то вдоль линий (Perl):

my %seen; 
@merged = grep { exists $seen{$_} ? 0 : ($seen{$_} = 1) } (map {(@$_)} @inputs);