如何合并两个列表并在“线性"时间内对其进行排序? [英] How can I merge two lists and sort them working in 'linear' time?

问题描述

我有这个，它有效:

# 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

但是，我真的很想好好学习这些东西. :)线性"时间是什么意思?

But, I'd really like to learn this stuff well. :) What does 'linear' time mean?

推荐答案

线性表示大O符号，而您的代码使用的是sort()，很可能是O(nlogn).

Linear means O(n) in Big O notation, while your code uses a sort() which is most likely O(nlogn).

问题是要使用标准合并算法.一个简单的Python实现是:

The question is asking for the standard merge algorithm. A simple Python implementation would be:

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]

这篇关于如何合并两个列表并在“线性"时间内对其进行排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！