Mô phỏng thuật toán Tích trừ chính nó

Product Except Self · Nhóm: Mảng

Tính result[i] = tích mọi phần tử trừ a[i], không dùng phép chia, chỉ với hai lượt duyệt.

Ý tưởng

Lượt trái sang phải: đặt result[i] bằng tích các phần tử đứng trước i (tích tiền tố).

Lượt phải sang trái: nhân dồn result[i] với tích các phần tử đứng sau i (tích hậu tố).

Sau hai lượt, mỗi ô là tích trái nhân tích phải, đúng bằng tích trừ chính nó.

Vì sao đúng

Tránh phép chia (an toàn khi có số 0 trong mảng) mà vẫn đạt O(n) · dùng chính mảng kết quả làm bộ nhớ tích lũy nên chỉ tốn O(1) bộ nhớ phụ ngoài đầu ra.

Mã Python

def product_except_self(a):
    n = len(a)
    result = [1] * n
    prefix = 1
    for i in range(n):          # left-to-right pass
        result[i] = prefix      # product of a[0..i-1]
        prefix *= a[i]
    suffix = 1
    for i in range(n - 1, -1, -1):   # right-to-left pass
        result[i] *= suffix     # times product of a[i+1..]
        suffix *= a[i]
    return result

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.