Союз перевернутых списков

Question

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

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);