有什么办法优化这个合并排序功能吗?你知道吗
输入是这样一个列表:[(1,'i'),(3,'i'),(5,'i'),(8,'i'),[(2,'n'),[(4,'t'),(7,'t'),[(6,'a'),[(9,'v'),[(10,'e')]],输出是单词:“主动”
def merge(decks):
while len(decks) > 1:
del1 = decks.pop(0)
del2 = decks.pop(0)
total = list()
while (len(del1) and len(del2)) > 0:
if del1[0] < del2[0]:
total.append(del1.pop(0))
else:
total.append(del2.pop(0))
total.extend(del1)
total.extend(del2)
decks.append(total)
word = ""
for kort in decks[0]:
word += kort[1]
return word
我可以想到一个优化:在内环之前同时反转
del[0]
和del[1]
,并将list.pop(0)
(an O(n) operation)更改为list.pop()
(在O(1)中)。反转也是O(n),但由于在循环内执行pop(0)
操作,因此实际上是O(n^2)
。你知道吗简单得多的方法是简单地展平列表,然后自然地对元组排序。你知道吗
from_iterable
展平嵌套列表sorted
根据每个元组的整数第一个元素,自然地对展平序列中的元组排序itemgetter(1)
是lambda x: x[1]
的有效实现imap
将访问函数应用于sorted
返回的列表,提取字母"".join
从提取的字母构建一个新字符串风格上稍微不那么“实用”的是使用列表理解,这是有意义的,因为
sorted
无论如何都返回一个列表,而不是更一般的迭代器。你知道吗您还可以使用
heapq
模块的merge
函数,它利用了每个嵌套列表已经排序的事实,而不是简单地对扁平列表排序。你知道吗相关问题 更多 >
编程相关推荐