Pythonで2つのソートされたリストをマージして、より大きなソートされたリストを形成するプログラム

ソートされたリストAとBが2つあるとします。それらをマージして、ソートされたリストCを1つだけ作成する必要があります。リストのサイズは異なる場合があります。

たとえば、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）のサイズの間、do
  • lst0 [i]> lst1 [j]の場合、
    • xの最後にlst1[j]を挿入します
    • j：=j + 1
  • それ以外の場合、lst0 [i]
  • xの最後にlst0[i]を挿入します
  • i：=i + 1
• それ以外の場合、
  • xの最後にlst0[i]を挿入します
  • xの最後にlst1[j]を挿入します
  • i：=i + 1、j：=j + 1

理解を深めるために実装を見てみましょう

例

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]