python - Python 列表的线性合并

Question

我正在处理 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() 将结果放回正确的位置命令。该解决方案在线性时间内有效，但更难看。

为什么这两个解决方案如此不同？我是否遗漏了什么，或者它们是否过于复杂？

Answer 1

他们鼓励您考虑合并两个排序列表的实际方法(算法)。假设你有两叠纸，上面写着名字，每叠都按字母顺序排列，你想把它们整理成一叠。您不会只是将它们放在一起然后从头开始分类；那将是太多的工作。您可以利用每堆已经排序的事实，因此您可以只从一堆中取出最先出现的那一个，然后将它们放入一个新的堆栈中。