python - 如何合并两个列表并在 'linear' 时间内对它们进行排序？

Question

我有这个，而且有效:

# 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):
  finalList = []
  for item in list1:
    finalList.append(item)
  for item in list2:
    finalList.append(item)
  finalList.sort()
  return finalList
  # +++your code here+++
  return

但是，我真的很想学好这些东西。 :) “线性”时间是什么意思？

Answer 1

线性表示 Big O notation 中的 O(n) ，而您的代码使用的 sort() 很可能是 O(nlogn)。

问题是要求 standard merge algorithm .一个简单的 Python 实现是:

def merge(l, m):
    result = []
    i = j = 0
    total = len(l) + len(m)
    while len(result) != total:
        if len(l) == i:
            result += m[j:]
            break
        elif len(m) == j:
            result += l[i:]
            break
        elif l[i] < m[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(m[j])
            j += 1
    return result

>>> merge([1,2,6,7], [1,3,5,9])
[1, 1, 2, 3, 5, 6, 7, 9]