合并ķ无序列表为一个并进行排序，然后将它们分开成K排序的列表？

Question

说我的K无序列表，我想将它们合并到一个列表，这样我可以在上面运行我的排序算法，然后我需要单独的这个大合并的列表以获得ķ排序列表。我怎么能跟踪哪些元素属于该列表，这样我可以分开这个正确合并列表？它需要线性的时间内完成

Answer 1

比方说，我们有n元素

初始化： 对于每个列表中的每个元素添加一个int，说哪个列出它所属。遍历所有O(n)。

合并： 对于每个列表，请其最终并使其指向下一个的开始。总时间O(n)。

打破： 创建k指针 - 新k lists的开始。 遍历排序列表和列表中的每个元素复制到列表的末尾它说，它属于从新k lists来。 我们能记住每一个新的列表的末尾，以便将采取O(1)到达那里。 O(n)的所以总时间。

和SUM所有的时间在一起 - O(n)。

Answer 2

使用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)时间来运行，这是你期待什么。