如何合并两个排序列表？

Question

我应该编写一个代码来合并排序列表，我在第二个函数中遇到一个错误：

TypeError: object of type 'NoneType' has no len()

我的代码是：

def merge(lst1, lst2):
    """ merging two ordered lists using
        the three pointer algorithm """
    n1 = len(lst1)
    n2 = len(lst2)
    lst3 = [0 for i in range(n1 + n2)]  # alocates a new list
    i = j = k = 0  # simultaneous assignment

    while (i < n1 and j < n2):
        if (lst1[i] <= lst2[j]):
            lst3[k] = lst1[i]
            i = i +1
        else:
            lst3[k] = lst2[j]
            j = j + 1
        k = k + 1  # incremented at each iteration
    lst3[k:] = lst1[i:] + lst2[j:]  # append remaining elements

def multi_merge_v3(lst_of_lsts):
     m = len(lst_of_lsts)
     merged = []
     for i in range(m):
          merged= merge((merged),(lst_of_lsts)[i])
     return(merged)

这个错误是什么意思？

我应该在代码中修复什么？

Answer 1

你没有从函数merge()返回任何东西，所以默认情况下它返回你分配给merged的None。所以，在第二次打电话给merge()时，你会做len(None)。

 for i in range(m):
      #Assigning None here 
      merged = merge(merged, lst_of_lsts[i])
 return(merged)

所以，在该功能的最后：

return lst3

Answer 2

这是对排序列表合并问题的简单看法。

l1 = [1,12,15,26,38]
l2 = [2,13,17,30,45,50]

# merged list
ml= [0]*(len(l1)+len(l2))


i1 = i2 = 0
for i in range(len(l1)+len(l2)): 
    if i1 == len(l1): 
        ml = ml[:i] + l2[i2:] 
        break
    if i2 == len(l2):
        ml = ml[:i] + l1[i1:]
        break       

    if l1[i1] < l2[i2]:
        ml[i] = l1[i1]
        i1 = i1 + 1
    else:
        ml[i] = l2[i2]
        i2 = i2 + 1 

print ml

Answer 3

这是一个选项：依赖Python的内置sorted函数：

merged = sorted(lst1 + lst2)

Answer 4

这是另一个答案：使用heapq的“合并”功能：

import heapq

merged = heapq.merge(lst1, lst2)

这是非常有效的，因为合并期望lst1和lst2已经被排序，所以它只查看第一个元素。

请注意，merge还允许多个（已排序）参数：

merged = heapq.merge(lst1, lst2, lst3, lst4)

在这一点上，merged实际上本身就是一个迭代器。要获得实际列表，请使用：

merged = list(heapq.merge(lst1, lst2))

请记住：使用Python，“包含电池”。