Product of Array Except Self

Q: Mengapa pembagian tidak diperbolehkan dalam Product of Array Except Self?

Membagi hasil kali total dengan nums[i] tidak berhasil jika array berisi angka nol: hasil kalinya 0, dan indeks angka nol itu sendiri memerlukan pembagian dengan 0. Untuk memperbaikinya, kamu perlu menghitung jumlah angka nol dan menangani kasus khusus. Hasil kali awalan dan akhiran menangani angka nol tanpa kasus khusus.

SedangPrefix sum

+10

Kamu mendapatkan array bilangan bulat nums. Kembalikan array answer dengan panjang yang sama, dengan answer[i] sebagai hasil kali setiap elemen nums kecuali elemen pada indeks i. Lakukan dalam waktu O(n) dan tanpa menggunakan pembagian.

Fungsi

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

numsinteger-array: array bilangan bulat, dengan setidaknya dua elemen
Mengembalikaninteger-array: array yang nilainya pada indeks i adalah hasil kali semua elemen kecuali nums[i]

Batasan

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
Hasil kali semua nilai bukan nol dalam nums muat dalam bilangan bulat bertanda 32-bit, jadi setiap hasil kali yang kamu hitung juga muat.

Contoh

Input: nums = [2, 3, 4, 5]
Output: [60, 40, 30, 24]
Penjelasan: Jika 2 tidak disertakan, hasilnya 3 × 4 × 5 = 60. Jika 3, 4, atau 5 tidak disertakan, hasilnya berturut-turut 40, 30, dan 24 dengan cara yang sama.

Pertanyaan lanjutan

Bisakah kamu hanya menggunakan ruang tambahan O(1), tanpa menghitung array yang kamu kembalikan?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Hasil kali semua nilai selain nums[i] adalah hasil kali nilai di sebelah kirinya dikali hasil kali nilai di sebelah kanannya. Hasil kali awalan dan akhiran menghasilkan semuanya dalam dua kali lintasan tanpa pembagian, sehingga nilai nol tidak memerlukan penanganan khusus. array output dapat menampung hasil kali di sebelah kiri, dan satu variabel dapat menampung hasil kali di sebelah kanan.

Kalikan yang lainnya untuk setiap indeks

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Untuk setiap indeks i, mulai dengan hasil perkalian bernilai 1, lalu kalikan dengan setiap nums[j] dengan j yang tidak sama dengan i. Melewati indeks i, alih-alih membaginya nanti, membuat nilai nol tidak menjadi masalah. Masing-masing dari n posisi memerlukan n-1 perkalian, sekitar 10^8 saat n = 10^4, dan hasil perkalian untuk indeks yang bersebelahan memiliki semua nilai yang sama kecuali dua.

Algoritma

Buat array jawaban dengan panjang n.
Untuk setiap indeks i, atur product ke 1.
Kalikan product dengan setiap nums[j] yang indeksnya j bukan i.
Simpan product pada indeks i dalam jawaban.
Kembalikan jawaban.

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

Array hasil kali prefiks dan sufiks

Intuisi

Sebut hasil kali nilai sebelum indeks i sebagai before[i], dan hasil kali nilai setelahnya sebagai after[i]. Lalu answer[i] = before[i] × after[i], dan nums[i] tidak disertakan tanpa melakukan pembagian.

Setiap array berkembang dari tetangganya dengan satu perkalian. before[0] adalah 1, hasil kali tanpa nilai apa pun, dan before[i] = before[i-1] × nums[i-1]; after mencerminkannya dari ujung kanan. Untuk [2, 3, 4, 5], kamu mendapatkan before = [1, 2, 6, 24] dan after = [60, 20, 5, 1], yang hasil kalinya adalah [60, 40, 30, 24]. Kedua array pembantu ini membutuhkan memori tambahan O(n).

Algoritma

Isi before dari kiri: before[0] = 1, lalu setiap entri adalah entri sebelumnya dikali nilai sebelumnya.
Isi after dari kanan: after[n-1] = 1, lalu setiap entri adalah entri berikutnya dikali nilai berikutnya.
Tetapkan answer[i] ke before[i] × after[i] untuk setiap indeks.
Kembalikan 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)]

Produk kiri di jawaban, satu produk kanan yang berjalan

Intuisi

Berjalan dari ujung kanan, hasil kali nilai setelah indeks i adalah satu angka, jadi kamu tidak memerlukan seluruh array after. Simpan nilainya dalam variabel right dan perbarui dengan satu perkalian setiap langkah.

Tulis hasil kali dari kiri langsung ke array jawaban. Saat berjalan kembali, kalikan answer[i] dengan right sebelum mengalikan right dengan nums[i]: saat menggunakan right pada indeks i, nilainya belum boleh mencakup nums[i]. Untuk [2, 3, 4, 5], nilai right adalah 1, 5, 20, dan 60 masing-masing pada indeks 3, 2, 1, dan 0. Selain array yang kamu kembalikan, memori tambahan yang diperlukan hanya satu variabel.

Algoritma

Tetapkan answer[0] = 1, lalu dari kiri ke kanan tetapkan answer[i] = answer[i-1] × nums[i-1].
Tetapkan right ke 1.
Dari indeks terakhir turun hingga 0, kalikan answer[i] dengan right.
Lalu kalikan right dengan nums[i].
Kembalikan 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

Jebakan dan kasus tepi

Membagi hasil kali total dengan nums[i]. Untuk [-2, 5, 0, 3], hasil kali totalnya 0, dan indeks 2 akan memerlukan pembagian 0 dengan 0.
Mengalikan right dengan nums[i] sebelum menggunakannya, sehingga nums[i] ikut masuk ke dalam hasil kalinya sendiri. Untuk [2, 3, 4, 5], nilai terakhir menjadi 120, bukan 24.
Memulai hasil kali di sebelah kiri dari nums[0], bukan 1. Tidak ada nilai di sebelah kiri indeks 0, jadi hasil kali di sebelah kirinya adalah 1. Jika tidak, [2, 3, 4, 5] menghasilkan 120 pada indeks 0, bukan 60.
Batas perulangan. Iterasi dari kiri membaca nums[i-1], jadi dimulai dari indeks 1; array sufiks membaca nums[i+1], jadi dimulai dari indeks n-2.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Product of Array Except Self?

Solusi awalan dan akhiran berjalan dalam waktu O(n), dengan satu lintasan dari setiap ujung. Dengan hasil kali dari kiri di array output dan satu hasil kali dari kanan yang terus diperbarui, solusi ini membutuhkan ruang ekstra O(1) selain output. Mengalikan semua nilai lainnya untuk setiap indeks membutuhkan waktu O(n²).

Mengapa pembagian tidak diperbolehkan dalam Product of Array Except Self?

Membagi hasil kali total dengan nums[i] tidak berhasil jika array berisi angka nol: hasil kalinya 0, dan indeks angka nol itu sendiri memerlukan pembagian dengan 0. Untuk memperbaikinya, kamu perlu menghitung jumlah angka nol dan menangani kasus khusus. Hasil kali awalan dan akhiran menangani angka nol tanpa kasus khusus.

Apakah array output dihitung sebagai ruang ekstra?

Tidak. Kamu tetap harus mengembalikan jawabannya, jadi konvensi yang umum tidak memasukkannya dalam hitungan ruang. Menyimpan hasil perkalian di sebelah kiri di dalamnya dan menyimpan hasil perkalian di sebelah kanan dalam satu variabel dihitung sebagai ruang tambahan O(1).

def productExceptSelf(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [2, 3, 4, 5]

Output yang diharapkan

[60, 40, 30, 24]

Product of Array Except Self

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Kalikan yang lainnya untuk setiap indeks

Array hasil kali prefiks dan sufiks

Produk kiri di jawaban, satu produk kanan yang berjalan

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa