Python 中列表的线性合并

Question

我正在做Google 的 Python 课程练习。其中一个练习是这样的：

给定两个按升序排序的列表，创建并返回按排序顺序的所有元素的合并列表。您可以修改传入的列表。理想情况下，该解决方案应在“线性”时间内工作，对两个列表进行一次传递。

我想出的解决方案是：

    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) 从每个列表中删除最后的元素，构建一个向后的解决方案列表。然后使用reverse()将结果恢复到正确的顺序。该解决方案在线性时间内有效，但更难看。

为什么这两种解决方案如此不同？我是否遗漏了什么，或者它们是否不必要地复杂？

Answer 1

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