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)의 크기, 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]