Python中列表的线性合并

5 投票

8 回答

9883 浏览

提问于 2025-04-17 00:36

我正在做谷歌的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)从每个列表的末尾移除元素，这样构建出的结果列表是反向的。然后用reversed()把结果再放回正确的顺序。这个方案是线性时间的，但看起来更复杂。

这两种解决方案为什么差别这么大？我是不是漏掉了什么，还是他们把事情搞得太复杂了？

数据结构算法优化复杂度分析列表合并元素遍历结果排序线性时间升序排列

8 个回答

我最喜欢@Abhijit的方法。这里有一个稍微更符合Python风格、更易读的代码版本：

def linear_merge(list1, list2):
    result = []

    while list1 and list2:
        result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))

    return (result + list1 + list2)[-1::-1]

借助Python内置的功能，我们可以：

不需要用len函数来明确检查列表是否为空。
可以合并或添加空列表，结果不会改变，所以也不需要特别检查。
我们可以把多个语句合并在一起（如果这样更易读的话），有时候这样能让代码更简洁。

回答于 2025-04-17 由 Python大师

分享举报

正如你所注意到的，你的解决方案运行得很好。那么，为什么会有复杂性呢？首先，

理想情况下，解决方案应该在“线性”时间内工作，也就是说只需遍历一次两个列表。

其实，你并没有明确地遍历任何列表，但你确实调用了 sorted()。那么 sorted() 会对列表进行多少次遍历呢？

其实我也不太清楚。通常，一个排序算法的运行时间大概是 O(n*log(n))，不过看看Python文档里的这句话：

Python中使用的Timsort算法能够高效地进行多次排序，因为它可以利用数据集中已经存在的任何排序。

也许有了解timsort的人能算出来。

但在这个解决方案中，他们利用了一个事实，那就是他们知道有两个已排序的列表。因此，他们并不是从“头开始”用 sorted，而是一个一个地挑选元素。

回答于 2025-04-17 由 Python大师

分享举报

他们鼓励你考虑一下合并两个已经排好序的列表的具体方法（算法）。假设你有两叠纸，上面写着名字，都是按字母顺序排好的，现在你想把它们合并成一叠有序的纸。你不会把这两叠纸随便放在一起，然后再从头开始排序；那样太麻烦了。你可以利用每一叠纸已经排好序的这个特点，只需从其中一叠中拿出最前面的纸，然后放到新的叠里，这样就能轻松合并了。

回答于 2025-04-17 由 Python大师

分享举报

Python中列表的线性合并

8 个回答

撰写回答