Chương trình trộn hai danh sách đã sắp xếp thành một danh sách lớn đã sắp xếp trong Python

Cho hai danh sách đã sắp xếp A và B, trộn thành một danh sách C đã sắp xếp. Kích thước có thể khác nhau.

Ví dụ

Đầu vào: A = [1,2,4,7], B = [1,3,4,5,6,8].
Đầu ra: [1,1,2,3,4,4,5,6,7,8].

Thuật toán

1. Khởi tạo x = [], i = j = 0.
2. Khi i < len(A) và j < len(B):
   • Nếu A[i] > B[j]: thêm B[j], j++.
   • Nếu A[i] < B[j]: thêm A[i], i++.
   • Ngược lại: thêm cả hai, i++, j++.
3. Thêm phần còn lại của A và B.
4. Trả về x.

Mã nguồn Python

class Solution:
    def solve(self, lst0, lst1):
        x = []
        i = j = 0
        while i < len(lst0) and j < len(lst1):
            if lst0[i] > lst1[j]:
                x.append(lst1[j])
                j += 1
            elif lst0[i] < lst1[j]:
                x.append(lst0[i])
                i += 1
            else:
                x.append(lst0[i])
                x.append(lst1[j])
                i += 1
                j += 1
        while i < len(lst0):
            x.append(lst0[i])
            i += 1
        while j < len(lst1):
            x.append(lst1[j])
            j += 1
        return x

ob = Solution()
print(ob.solve([1,2,4,7], [1,3,4,5,6,8]))

Đầu vào / Đầu ra

Input: [1,2,4,7], [1,3,4,5,6,8]
Output: [1, 1, 2, 3, 4, 4, 5, 6, 7, 8]