Python程序：合并两个已排序列表以形成更大的已排序列表

假设我们有两个已排序的列表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 := 新列表
  • i := 0, j := 0
  • 当 i < lst0 的大小 且 j < lst1 的大小 时，执行以下操作：
    • 如果 lst0[i] > lst1[j]，则
      • 将 lst1[j] 插入到 x 的末尾
      • j := j + 1
    • 否则，当 lst0[i] < lst1[j] 时，则
      • 将 lst0[i] 插入到 x 的末尾
      • i := i + 1
    • 否则，
      • 将 lst0[i] 插入到 x 的末尾
      • 将 lst1[j] 插入到 x 的末尾
      • i := i + 1, j := j + 1
  • 当 i < len(lst0) 时，执行以下操作：
    • 将 lst0[i] 插入到 x 的末尾
    • i := i + 1
  • 当 j < len(lst1) 时，执行以下操作：
    • 将 lst1[j] 插入到 x 的末尾
    • j := j + 1
  • 返回 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]))

输入

[1,2,4,7], [1,3,4,5,6,8]

输出

[1, 1, 2, 3, 4, 4, 5, 6, 7, 8]

更新于：2020年10月6日

浏览量：172

开启您的职业生涯

完成课程后获得认证

开始学习
广告