我在线性时间内合并两个排序列表的实现-有什么可以改进的地方？

一尘不染

我在线性时间内合并两个排序列表的实现-有什么可以改进的地方？

algorithm

Fromg Google的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):
  merged_list = []
  i = 0
  j = 0

  while True:
    if i == len(list1):
        return merged_list + list2[j:]
    if j == len(list2):
        return merged_list + list1[i:]

    if list1[i] <= list2[j]:
        merged_list.append(list1[i])
        i += 1
    else:
        merged_list.append(list2[j])
        j += 1

首先，可以在此处使用无限循环吗？合并列表后，应该使用break关键字打破循环吗？还是可以在这里返回？

我在这里看到过类似的问题，所有解决方案看上去都与我的相似，即非常类似于C。不再有类似python的解决方案吗？还是因为算法的性质？

阅读 309

2020-07-28

共1个答案

一尘不染

这个问题比您可能需要的更为详尽。;）选择的答案符合您的要求。如果我需要自己执行此操作，则可以按照dbr在他或她的答案中描述的方式进行操作（将列表添加在一起，对新列表进行排序），因为它非常简单。

编辑：

我在下面添加一个实现。我实际上在这里似乎已被删除的另一个答案中看到了这一点。我只是希望它没有被删除，因为它有一个我没有发现的错误。;）

def mergeSortedLists(a, b):
    l = []
    while a and b:
        if a[0] < b[0]:
            l.append(a.pop(0))
        else:
            l.append(b.pop(0))
    return l + a + b

2020-07-28