Hợp nhất mảng đã sắp xếp trong Python

Cho hai mảng đã sắp xếp A, B. Hợp nhất thành một mảng đã sắp xếp C. Ví dụ: A=[1,2,4,7], B=[1,3,4,5,6,8] → [1,1,2,3,4,4,5,6,7,8].

Giải pháp

Sử dụng hai con trỏ, dịch chuyển phần tử trong A (giả định A có đủ chỗ trống):

• i=0, j=0, end=len(A)-1.
• Di chuyển end đến phần tử cuối khác 0.
• Duyệt B: chèn vào A tại vị trí thích hợp, dịch các phần tử lớn hơn sang phải.

Ví dụ

Triển khai Python:

class Solution(object): 
    def merge(self, nums1, m, nums2, n): 
        i = 0 
        j = 0 
        end = len(nums1)-1 
        while end>=0 and not nums1[end]: 
            end-=1 
        while j<len(nums2) : 
            if i>end and not nums1[i]: 
                nums1[i] = nums2[j] 
                j+=1 
            elif nums1[i]>nums2[j]: 
                self.shift(nums1,i) 
                nums1[i] = nums2[j] 
                end+=1 
                j+=1 
            i+=1 
        return nums1 
    def shift(self,num,i): 
        j = len(num)-1 
        while not num[j]: 
            j-=1 
        while j>=i: 
            num[j+1] = num[j] 
            j-=1 
ob = Solution() 
print(ob.merge([1,2,3,0,0,0],3,[2,5,6],3))

Đầu vào

[1,2,3,0,0,0] [2,5,6]

Đầu ra

[1, 2, 2, 3, 5, 6]