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

但是，我真的很想把这些东西学好。：）线性时间是什么意思？

最佳答案

线性意味着O（n）inBig O notation，而您的代码使用的是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]

关于python - 如何合并两个列表并在“线性”时间内对其进行排序？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2488889/