Nhân Bản Số 0 (Duplicate Zeros) Trong Python

Cho mảng số nguyên độ dài cố định. Nhân bản mỗi số 0: chèn thêm 0 ngay sau nó, dịch các phần tử phía phải. Phần tử vượt quá độ dài mảng gốc bị loại bỏ.

Ví dụ: [1,0,2,3,0,4,5,0] → [1,0,0,2,3,0,0,4] (2 zero đầu nhân bản, zero cuối bị cắt do hết chỗ).

Thuật toán (O(n) time, O(n) space - dễ hiểu)

1. Sao chép mảng gốc → arr2
2. Duyệt arr2 với con trỏ j, ghi vào arr với con trỏ i
3. Nếu arr2[j] == 0: ghi 2 lần 0 vào arr[i], arr[i+1] (nếu còn chỗ)
4. Ngược lại: ghi arr2[j]

Ví dụ (Python)

class Solution(object):
    def duplicateZeros(self, arr):
        arr2 = arr[:]  # copy
        i = j = 0
        n = len(arr)
        while i < n:
            if arr2[j] == 0:
                arr[i] = 0
                i += 1
                if i < n:
                    arr[i] = 0
            else:
                arr[i] = arr2[j]
            i += 1
            j += 1
        return arr

ob1 = Solution()
print(ob1.duplicateZeros([1,0,2,3,0,4,5,0]))  # [1, 0, 0, 2, 3, 0, 0, 4]

Thuật toán O(1) space (In-place, 2 pass)

def duplicateZeros(arr):
    n = len(arr)
    zeros = arr.count(0)
    
    # Pass 1: xác định vị trí cuối cùng sẽ được ghi
    i = n - 1
    j = n + zeros - 1
    
    # Pass 2: ghi từ cuối về đầu
    while i >= 0:
        if j < n:
            arr[j] = arr[i]
        if arr[i] == 0:
            j -= 1
            if j < n:
                arr[j] = 0
        i -= 1
        j -= 1

Độ phức tạp

• Cách 1 (copy): O(n) time, O(n) space
• Cách 2 (in-place): O(n) time, O(1) space

Đầu vào / Đầu ra

Input:  [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]