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

開啟您的職業生涯

完成課程後獲得認證

開始學習
廣告