如何合并两个列表并在“线性”时间内对它们进行排序？
如何合并两个列表并在“线性”时间内对它们进行排序？
提问于 2010-03-22 05:55:15
我有这个，它起作用了：
# E. Given two lists sorted in increasing order, create and return a merged
# list of all the elements in sorted order. You may modify the passed in lists.
# Ideally, the solution should work in "linear" time, making a single
# pass of both lists.
def linear_merge(list1, list2):
finalList = []
for item in list1:
finalList.append(item)
for item in list2:
finalList.append(item)
finalList.sort()
return finalList
# +++your code here+++
return但是，我真的很想把这些东西学好。:)什么是“线性”时间？
回答 7
Stack Overflow用户
回答已采纳
发布于 2010-03-22 06:06:47
线性表示Big O notation中的O(n)，而您的代码使用的sort()很可能是O(nlogn)。
问题是询问standard merge algorithm。一个简单的Python实现是：
def merge(l, m):
result = []
i = j = 0
total = len(l) + len(m)
while len(result) != total:
if len(l) == i:
result += m[j:]
break
elif len(m) == j:
result += l[i:]
break
elif l[i] < m[j]:
result.append(l[i])
i += 1
else:
result.append(m[j])
j += 1
return result
>>> merge([1,2,6,7], [1,3,5,9])
[1, 1, 2, 3, 5, 6, 7, 9]Stack Overflow用户
发布于 2010-03-22 07:08:56
如果以反向排序的顺序构建结果，则可以使用pop()，但仍然是O(N)
列表右端的pop()不需要移位元素，O(1)也不需要移位
在返回之前颠倒列表是O(N)
>>> def merge(l, r):
... result = []
... while l and r:
... if l[-1] > r[-1]:
... result.append(l.pop())
... else:
... result.append(r.pop())
... result+=(l+r)[::-1]
... result.reverse()
... return result
...
>>> merge([1,2,6,7], [1,3,5,9])
[1, 1, 2, 3, 5, 6, 7, 9]Stack Overflow用户
发布于 2010-03-22 06:59:38
此线程包含线性时间合并算法的各种实现。请注意，出于实际目的，您将使用heapq.merge。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2488889
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号