用 Python 编写程序合并两个排序列表以形成更大的排序列表

pythonserver side programmingprogramming更新于 2026/1/11 0:44:17

假设我们有两个排序列表 A 和 B。我们必须合并它们并形成一个排序列表 C。列表的大小可能不同。

例如，假设 A = [1,2,4,7] 和 B = [1,3,4,5,6,8]，则合并后的列表 C 将为 [1,1,2,3,4,4,5,6,7,8]

我们将使用递归来解决这个问题。因此该函数将像下面这样工作 −

x:= a new list
i:= 0, j:= 0
while i < size of (lst0) and j < (lst1) 的大小，则执行
- 如果 lst0[i] > lst1[j]，则
  - 在 x 的末尾插入 lst1[j]
  - j:= j+1
- 否则，当 lst0[i]<lst1[j] 时，则
  - 在 x 的末尾插入 lst0[i]
  - i:= i+1
- 否则，
  - 在 x 的末尾插入 lst0[i]
  - 在 x 的末尾插入 lst1[j]
  - i:= i+1, j:= j+1
当 i<len(lst0) 时，执行
- 在 x 的末尾插入 lst0[i]
- i:= i+1
当 j<len(lst1) 时，执行
- 在 x 的末尾插入 lst1[j]
- j:= j+1
return x

让我们看一下实现过程以便更好地理解

示例

class Solution:
   def solve(self, lst0, lst1):
      x=[]
      i=0
      j=0
      while(i<len(lst0) and j<len(lst1)):
         if(lst0[i]>lst1[j]):
            x.append(lst1[j])
            j=j+1
         elif(lst0[i]<lst1[j]):
            x.append(lst0[i])
            i=i+1
         else:
            x.append(lst0[i])
            x.append(lst1[j])
            i=i+1
            j=j+1
      while(i<len(lst0)):
         x.append(lst0[i])
         i=i+1
      while(j<len(lst1)):
         x.append(lst1[j])
         j=j+1
      return x
ob = Solution()
print(ob.solve([1,2,4,7], [1,3,4,5,6,8]))