Объединить k несортированных списков в один и отсортировать их, а затем разделить их на k отсортированных списков?

Question

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

Answer 1

Используя диктонар в Python, это можно сделать очень легко.

from collections import OrderedDict
a = [[9,2,5],[6,3,7],[1,8,4]]  #3 unsorted lists with 3 elements in each.
​
key_dict = dict()            # create a dictonary
​
for i in range(len(a)):      # iterate over each nested-list
    for val in a[i]:         # iterate over each element of the nested list
        key_dict[val] = i    # each element in dict contains the index of the nested list 
                             # it belongs to as a value, the key is the element itself
​
​
sorted_dict = OrderedDict(sorted(key_dict.items(), key=lambda x: x[0])) #sorting elements collectively
​
new_list = [[] for i in range(3)]       # you can change it to number of nested lists present.
​
for k, v in sorted_dict.items():
    new_list[v].append(k)
print(new_list)     # Output : [[2, 5, 9], [3, 6, 7], [1, 4, 8]]

Кроме сортировки элементов, каждый шаг занимает O(n) время выполнения, и это точно то, что вы ожидали.

Answer 2

Допустим, у нас есть n элементов

Initialize:
Для каждого элемента в каждом списке добавьте int, который говорит, к какому списку он принадлежит.Переберите все O(n).

Слияние:
Для каждого списка перейдите к его концу и укажите начало следующего.Общее время O(n).

Перерыв:
Создать k указатели - начало нового k lists.
Перебрать отсортированный список и для каждого элемента в списке скопировать его вконец списка, к которому он принадлежит, из нового k lists.
Мы можем запомнить конец каждого из новых списков, поэтому для его достижения потребуется O(1).Таким образом, общее время O(n).

И сумма все время вместе - O(n).