Product of Array Except Self

Q: Tại sao không được phép dùng phép chia trong Tích của mảng trừ chính nó?

Chia tích của toàn bộ mảng cho nums[i] sẽ gây lỗi khi mảng có số 0: tích của toàn bộ mảng bằng 0, và tại chỉ số của số 0, phép chia cần thực hiện là chia cho 0. Để khắc phục, cần đếm số 0 và xử lý các trường hợp đặc biệt. Tích tiền tố và hậu tố xử lý số 0 mà không cần trường hợp đặc biệt.

Trung bìnhTổng tiền tố

+10

Bạn nhận được một mảng số nguyên nums. Hãy trả về một mảng answer có cùng độ dài, trong đó answer[i] là tích của mọi phần tử trong nums ngoại trừ phần tử ở chỉ số i. Hãy thực hiện trong thời gian O(n) và không dùng phép chia.

Hàm

productExceptSelf(nums: integer-array) → integer-array

numsinteger-array: mảng số nguyên có ít nhất hai phần tử
Trả vềinteger-array: một mảng có giá trị tại chỉ số i là tích của tất cả phần tử ngoại trừ nums[i]

Ràng buộc

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
Tích của tất cả giá trị khác 0 trong nums nằm trong phạm vi của một số nguyên (integer) có dấu 32 bit, vì vậy mọi tích bạn tính trong quá trình thực hiện cũng nằm trong phạm vi đó.

Ví dụ

Đầu vào: nums = [2, 3, 4, 5]
Đầu ra: [60, 40, 30, 24]
Giải thích: Bỏ số 2 thì còn 3 × 4 × 5 = 60. Tương tự, bỏ số 3, số 4 hoặc số 5 thì lần lượt được 40, 30 và 24.

Câu hỏi mở rộng

Bạn có thể chỉ dùng thêm không gian O(1), không tính mảng mà bạn trả về không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Tích của mọi giá trị ngoại trừ nums[i] bằng tích các giá trị ở bên trái nhân với tích các giá trị ở bên phải. Tích tiền tố và hậu tố cho ta tất cả các tích đó qua hai lượt duyệt mà không cần phép chia, nên không cần xử lý riêng các số 0. Mảng đầu ra có thể chứa các tích bên trái, còn một biến chứa tích bên phải.

Nhân các phần tử còn lại theo từng chỉ số

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Với mỗi chỉ số i, bắt đầu tích bằng 1 rồi nhân lần lượt với từng nums[j] có j khác i. Bỏ qua chỉ số i thay vì chia bỏ nó sau này giúp các số 0 không gây vấn đề. Mỗi trong số n vị trí cần n-1 phép nhân, khoảng 10^8 khi n = 10^4, và tích của các chỉ số liền kề có tất cả giá trị chung, trừ hai giá trị.

Thuật toán

Tạo một mảng kết quả có độ dài n.
Với mỗi chỉ số i, đặt product thành 1.
Nhân product với mọi nums[j] có chỉ số j khác i.
Lưu product tại chỉ số i trong mảng kết quả.
Trả về mảng kết quả.

def productExceptSelf(nums):
    n = len(nums)
    answer = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer.append(product)
    return answer

Mảng tích các tiền tố và hậu tố

Ý tưởng

Gọi tích các giá trị trước chỉ số i là before[i], và tích các giá trị sau chỉ số đó là after[i]. Khi đó, answer[i] = before[i] × after[i], còn nums[i] được bỏ qua mà không cần phép chia nào.

Mỗi mảng được tính từ phần tử bên cạnh bằng một phép nhân. before[0] bằng 1, là tích của không giá trị nào, và before[i] = before[i-1] × nums[i-1]; after làm tương tự từ đầu bên phải. Với [2, 3, 4, 5], ta có before = [1, 2, 6, 24] và after = [60, 20, 5, 1], tích của chúng là [60, 40, 30, 24]. Hai mảng phụ cần thêm bộ nhớ O(n).

Thuật toán

Điền before từ trái sang phải: before[0] = 1, sau đó mỗi phần tử bằng phần tử trước đó nhân với giá trị trước đó.
Điền after từ phải sang trái: after[n-1] = 1, sau đó mỗi phần tử bằng phần tử tiếp theo nhân với giá trị tiếp theo.
Đặt answer[i] bằng before[i] × after[i] cho mọi chỉ số.
Trả về answer.

def productExceptSelf(nums):
    n = len(nums)
    # before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
    before = [1] * n
    after = [1] * n
    for i in range(1, n):
        before[i] = before[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        after[i] = after[i + 1] * nums[i + 1]
    return [before[i] * after[i] for i in range(n)]

Các tích bên trái trong đáp án, một tích đang chạy ở bên phải

Ý tưởng

Đi từ cuối mảng về đầu, tích các giá trị sau chỉ số i là một số duy nhất, nên bạn không cần toàn bộ mảng after. Lưu giá trị đó vào biến right và cập nhật nó bằng một phép nhân ở mỗi bước.

Ghi trực tiếp các tích bên trái vào mảng kết quả. Khi đi ngược lại, hãy nhân answer[i] với right trước khi nhân right với nums[i]: khi dùng right tại chỉ số i, giá trị này chưa được chứa nums[i]. Với [2, 3, 4, 5], right lần lượt là 1, 5, 20 và 60 tại các chỉ số 3, 2, 1 và 0. Ngoài mảng bạn trả về, bộ nhớ phụ chỉ cần một biến.

Thuật toán

Đặt answer[0] = 1, sau đó duyệt từ trái sang phải và đặt answer[i] = answer[i-1] × nums[i-1].
Đặt right bằng 1.
Duyệt từ chỉ số cuối cùng xuống 0, nhân answer[i] với right.
Sau đó, nhân right với nums[i].
Trả về answer.

def productExceptSelf(nums):
    n = len(nums)
    # Pass 1: answer[i] = product of everything left of i
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
    # Pass 2: multiply in the product of everything right of i
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

Lỗi thường gặp và trường hợp biên

Chia tích tổng cho nums[i]. Với [-2, 5, 0, 3], tích tổng là 0, và ở chỉ số 2 sẽ cần tính 0 chia cho 0.
Nhân right với nums[i] trước khi dùng nó, khiến nums[i] được tính vào tích của chính nó. Với [2, 3, 4, 5], giá trị cuối cùng trở thành 120 thay vì 24.
Bắt đầu tích bên trái bằng nums[0] thay vì 1. Không có gì nằm bên trái chỉ số 0, nên tích bên trái của nó là 1; nếu không, [2, 3, 4, 5] sẽ cho kết quả 120 tại chỉ số 0 thay vì 60.
Giới hạn vòng lặp. Lượt duyệt từ trái sang phải đọc nums[i-1], nên bắt đầu ở chỉ số 1; mảng hậu tố đọc nums[i+1], nên bắt đầu ở chỉ số n-2.

Câu hỏi thường gặp3

Độ phức tạp thời gian của tích các phần tử trong mảng, ngoại trừ chính nó, là bao nhiêu?

Lời giải dùng tiền tố và hậu tố chạy trong thời gian O(n), với một lượt duyệt từ mỗi đầu. Khi các tích từ bên trái nằm trong mảng đầu ra và chỉ cần một tích bên phải được cập nhật liên tục, lời giải cần O(1) bộ nhớ bổ sung ngoài mảng đầu ra. Nhân tất cả các giá trị còn lại cho mỗi chỉ số sẽ mất thời gian O(n²).

Tại sao không được phép dùng phép chia trong Tích của mảng trừ chính nó?

Chia tích của toàn bộ mảng cho nums[i] sẽ gây lỗi khi mảng có số 0: tích của toàn bộ mảng bằng 0, và tại chỉ số của số 0, phép chia cần thực hiện là chia cho 0. Để khắc phục, cần đếm số 0 và xử lý các trường hợp đặc biệt. Tích tiền tố và hậu tố xử lý số 0 mà không cần trường hợp đặc biệt.

Mảng đầu ra có được tính là không gian phụ không?

Không. Dù sao bạn cũng phải trả về đáp án, nên quy ước thông thường không tính phần đó vào dung lượng bộ nhớ. Lưu các tích bên trái vào đó và giữ tích bên phải trong một biến được tính là dung lượng bộ nhớ bổ sung O(1).

def productExceptSelf(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [2, 3, 4, 5]

Đầu ra mong đợi

[60, 40, 30, 24]

Product of Array Except Self

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Nhân các phần tử còn lại theo từng chỉ số

Mảng tích các tiền tố và hậu tố

Các tích bên trái trong đáp án, một tích đang chạy ở bên phải

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự