如何在线性时间内合并python中的两个排序列表(只遍历一次)？

Question

list_a = [1,7,9,35,36,37]
list_b = [3,4,5,40]

预期输出：

list_merged = [1,3,4,5,7,9,35,36,37,40]

条件:只能遍历两个列表一次

我知道zip，它的工作原理如下，非常符合我的要求。

>>> x = [1, 2]
>>> y = [1, 3, 4, 5, 6]
>>> zip(x,y)
[(1, 1), (2, 3)]
>>> zip(y, x)
[(1, 1), (3, 2)]

Answer 1

这是我自己尝试过的。解决方案并不是很短，但是是一个简单的吗..

def linear_merge(list1, list2):
  i = 0
  j = 0
  list_m = [] # resultant list

  while i < len(list1) and j < len(list2):
    if list1[i] <= list2[j]: #take element from list 1 
      list_m.append(list1[i])
      i += 1
    else: # or take element from list 2
      list_m.append(list2[j])
      j += 1

  if i <= len(list1) - 1: #append remaing elements from list 1 
    list_m.extend(list1[i:])
  elif j <= len(list2) - 1: #or append remaing elements from list 2
    list_m.extend(list2[j:])

  return list_m

在我看来，这是直接有效的C方式。还有更多的pythonic解决方案吗？

Answer 2

您可以使用不同的索引变量遍历这两个列表。

list_a = [1,7,9,35,36,37]
list_b = [3,4,5,40]
index_a = 0
index_b = 0
merged = []
while index_a<len(list_b) or index_b < len(list_b):
    if index_a<len(list_a) and list_a[index_a]<=list_b[index_b]:
        merged.append(list_a[index_a])
        index_a +=1
    elif index_b<len(list_b):
        merged.append(list_b[index_b])
        index_b +=1
print merged
# [1, 3, 4, 5, 7, 9, 35, 36, 37, 40]

Answer 3

方法是：

为每个列表保留两个指针(用于列表的索引)，并检查较小的元素。当找到较小的元素时，将指针移动到该列表的下一个元素。保持另一个(第二个列表)指针不变。因此，每个列表只能遍历一次。如果你实现了上面的方法，你唯一遗漏的就是最大的(最后)元素。所以又用了一个指针来保存最后一个元素。

希望这能有所帮助：

list_a = [1,7,9,35,36,37] # also works for list_a = [1,7,9,35,36,45]
list_b = [3,4,5,40]

ptr_a = 0 # pointer for a
ptr_b = 0 # pointer for b
last = 0 # pointer for last element
list_merged = [] # merged result list

while ptr_a<len(list_a) and ptr_b<len(list_b):
    if list_a[ptr_a] < list_b[ptr_b]:
        list_merged.append(list_a[ptr_a])
        ptr_a = ptr_a + 1
        last = list_b[ptr_b] # assign last element

    else:
        list_merged.append(list_b[ptr_b])
        ptr_b = ptr_b + 1
        last = list_a[ptr_a] # assign last element

# at the end of the while loop the last element of 
# the 'merged list' has not added. Below line is to add it.
list_merged.append(last)
print list_merged