Chương trình hợp nhất hai danh sách đã sắp xếp để tạo thành danh sách được sắp xếp lớn hơn bằng Python

Giả sử chúng ta có hai danh sách được sắp xếp A và B. Chúng ta phải hợp nhất chúng lại và chỉ tạo thành một danh sách được sắp xếp C. Kích thước của các danh sách có thể khác nhau.

Ví dụ:giả sử A =[1,2,4,7] và B =[1,3,4,5,6,8], thì danh sách hợp nhất C sẽ là [1,1,2,3,4, 4,5,6,7,8]

Chúng tôi sẽ giải quyết điều này bằng cách sử dụng đệ quy. Vì vậy, hàm sẽ hoạt động như bên dưới -

• x:=một danh sách mới
• i:=0, j:=0
• while i
• nếu lst0 [i]> lst1 [j], thì
  • chèn lst1 [j] vào cuối x
  • j:=j + 1
• ngược lại khi lst0 [i]
• chèn lst0 [i] vào cuối x
• i:=i + 1

Hãy cho chúng tôi xem việc triển khai để hiểu rõ hơn

Ví dụ

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]))

Đầu vào

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

Đầu ra

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