关于谷歌Python课程的解决方案问题

Question

嘿，

我正在学习一些Python，所以决定跟着谷歌的教程来学。不过我对他们一个练习的解法有个问题。

我这样做的。

# 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):
  # +++your code here+++
  return sorted(list1 + list2)

但是他们的做法要复杂一些。那么，谷歌的解法更快吗？因为我注意到评论里提到这个解法应该是“线性”时间的，而我的可能不是？

这是他们的解法。

def linear_merge(list1, list2):
  # +++your code here+++
  # LAB(begin solution)
  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

Answer 1

我觉得这里的问题在于，这个教程是在教你怎么用Python实现一个叫做“合并”的著名算法。教程并不希望你在解决方案中使用库里的排序函数。

sorted() 函数的复杂度大概是 O(nlgn)，所以在最坏情况下，你的解决方案不可能是线性的。

理解 merge() 是怎么工作的很重要，因为它在很多其他算法中都很有用。这个算法利用了输入列表已经排好序的特点，依次遍历每个列表，选择最小的那个。剩下的项会被加到最后面。

问题并不是哪个算法对特定输入更“快”，而是哪个算法更复杂。

还有一些混合版的合并排序算法，当输入列表的大小低于某个阈值时，会切换到其他排序算法。

Answer 2

这可能是另一种解决方案？

    def linear_merge(list1, list2):
            tmp = []
            while len(list1) and len(list2):
                    #print list1[-1],list2[-1]
                    if list1[-1] > list2[-1]:
                            tmp.append(list1.pop())
                    else:
                            tmp.append(list2.pop())
                    #print "tmp = ",tmp

            #print list1,list2
            tmp = tmp + list1
            tmp = tmp + list2
            tmp.reverse()
            return tmp

Answer 3

你的算法不是线性的，但这并不意味着它就一定更慢。算法的复杂度（也就是“大O表示法”）通常只是一个粗略的参考，它只能告诉你故事的一部分。

不过，他们的算法也不是线性的，虽然乍一看可能会觉得是。因为从列表中弹出一个元素时，需要移动后面的所有元素，所以从前面弹出一个元素时，就需要移动所有剩下的元素。

想一想如何把这个复杂度降低到O(n)是个不错的练习。下面的内容和给出的解决方案有相似之处，但避免了一些陷阱，同时为了练习扩展到不止两个列表。如果只有两个列表，你可以不使用堆，而是直接比较哪个下一个元素更小。

import heapq

def iter_linear_merge(*args):
  """Yield non-decreasing items from sorted a and b."""
  # Technically, [1, 1, 2, 2] isn't an "increasing" sequence,
  # but it is non-decreasing.

  nexts = []
  for x in args:
    x = iter(x)
    for n in x:
      heapq.heappush(nexts, (n, x))
      break

  while len(nexts) >= 2:
    n, x = heapq.heappop(nexts)
    yield n
    for n in x:
      heapq.heappush(nexts, (n, x))
      break

  if nexts:  # Degenerate case of the heap, not strictly required.
    n, x = nexts[0]
    yield n
    for n in x:
      yield n

在最后的if-for循环中，while循环的条件可以改成只检查“nexts”，但特别处理最后一个迭代器可能还是值得的。

如果你想严格返回一个列表而不是迭代器：

def linear_merge(*args):
  return list(iter_linear_merge(*args))