Python中列表的线性合并
我正在通过Google's Python class exercises工作。其中一个练习是这样的：
给定两个按升序排序的列表，创建并返回按排序顺序排列的所有元素的合并列表。您可以修改传入的列表。理想情况下，解决方案应该在“线性”时间内工作，对两个列表进行一次遍历。
我想出的解决方案是：
def linear_merge(list1, list2):
list1.extend(list2)
return sorted(list1)它通过了测试函数，但给出的解决方案是：
def linear_merge(list1, list2):
result = []
# Look at the two lists so long as both are non-empty.
# Take whichever element [0] is smaller.
while len(list1) and len(list2):
if list1[0] < list2[0]:
result.append(list1.pop(0))
else:
result.append(list2.pop(0))
# Now tack on what's left
result.extend(list1)
result.extend(list2)
return result包含在解决方案中的是：
注意:上面的解决方案有点可爱，但不幸的是list.pop(0)不是标准python列表实现的常量时间，所以上面的时间不是严格意义上的线性时间。另一种方法是使用pop(-1)从每个列表中删除最末端的元素，构建一个向后的解决方案列表。然后使用reversed()将结果放回正确的顺序。这种解决方案在线性时间内有效，但更丑陋。
为什么这两种解决方案如此不同？我是不是遗漏了什么，或者它们是不必要的复杂？
回答 6
Stack Overflow用户
发布于 2011-08-30 09:53:47
他们鼓励您思考合并两个排序列表的实际方法(算法)。假设你有两堆纸，上面都有名字，每一堆都是按字母顺序排列的，你想从它们中得到一个排序的堆栈。你不会简单地把它们放在一起，然后从头开始排序；那会有太多的工作。您可以利用每个堆已经排序的事实，因此您只需从一个堆或另一个堆中取出最先出现的一个，并将它们放入新的堆栈中。
Stack Overflow用户
发布于 2011-08-30 09:51:37
您的解决方案是O(n log n)，这意味着如果列表的长度是O(N Log N)的10倍，那么程序将花费(大约) 30倍的时间。他们的解决方案只需要10倍的时间。
Stack Overflow用户
发布于 2015-08-01 17:37:43
从列表的末尾弹出，直到其中一个为空。我认为这是线性的，反转也是线性的。丑陋，但却是一个解决方案。
def linear_merge(list1, list2):
# NOT return sorted (list1 + list2), as this is not linear
list3 = []
rem = []
empty = False
while not empty:
# Get last items from each list, if they exist
if len (list1) > 0:
a = list1[-1]
else:
rem = list2[:]
empty = True
if len (list2) > 0:
b = list2[-1]
else:
rem = list1[:]
empty = True
# Pop the one that's largest onto the new list
if not empty:
if a > b:
list3.append (a)
list1.pop ()
else:
list3.append (b)
list2.pop ()
# add the (reversed) remainder to the list
rem.reverse ()
list3 += rem
# reverse the entire list
list3.reverse ()
return list3https://stackoverflow.com/questions/7237875
复制相似问题