Product of Array Except Self

Q: Array Except Self çarpımında bölmeye neden izin verilmiyor?

Toplam çarpımı nums[i] değerine bölmek, dizi sıfır içerdiğinde işe yaramaz; çünkü toplam 0 olur ve sıfırın kendi indeksinde 0'a bölme işlemi gerekir. Bunu çalışır hâle getirmek için sıfırların sayısını tutmak ve özel durumları ele almak gerekir. Bu kural, sıfırları hiçbir özel durum gerektirmeden ele alan önek ve sonek çarpımlarını kullanmaya yönlendirir.

OrtaÖnek toplamı

+10

Bir tam sayılar dizisi nums veriliyor. answer dizisinin uzunluğu aynı olacak şekilde, answer[i] değerinin nums dizisindeki i indeksindeki eleman dışındaki tüm elemanların çarpımı olduğu bir dizi döndürün. Bunu O(n) zamanda ve bölme kullanmadan yapın.

Fonksiyon

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

numsinteger-array: en az iki eleman içeren tamsayı dizisi
Döndürürinteger-array: i indeksindeki değeri, nums[i] dışındaki tüm öğelerin çarpımı olan bir dizi

Kısıtlar

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
Sıfır olmayan tüm nums değerlerinin çarpımı 32 bitlik işaretli bir tam sayıya sığar; dolayısıyla yol boyunca oluşturduğun her çarpım da sığar.

Örnekler

Girdi: nums = [2, 3, 4, 5]
Çıktı: [60, 40, 30, 24]
Açıklama: 2'yi çıkardığımızda 3 × 4 × 5 = 60, 5'i çıkardığımızda ise 2 × 3 × 4 = 24 kalır. Ortadaki iki sayı için de aynı yöntem geçerlidir: 2 × 4 × 5 = 40 ve 2 × 3 × 5 = 30.

Gönderirken +14 gizli test

Ek soru

Geri döndürdüğün dizi hariç, yalnızca O(1) ek alan kullanabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

nums[i] dışındaki tüm değerlerin çarpımı, solundaki değerlerin çarpımı ile sağındaki değerlerin çarpımına eşittir. Toplam çarpımı nums[i] değerine bölmek daha kısa görünür, ancak burada buna izin verilmez ve toplamın 0 olduğu durumlarda, yani sıfırlar bulunduğunda, işe yaramaz. Önek ve sonek çarpımları, iki geçişte soldaki ve sağdaki tüm çarpımları verir; böylece çözüm O(n) zaman alır. Çıktı dizisi sol çarpımları tutabilir ve tek bir değişken sağ çarpımı taşıyabilir; bu nedenle başka bir diziye gerek yoktur.

Her indeks için diğerlerini çarpın

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Tanımı izleyin. Her i indisi için çarpımı 1’den başlatın ve indisi i olmayan her nums[j] değerini çarpıma dahil edin. Bu indisi atlamak, sonradan bölerek çıkarmak yerine, sıfırları sorun olmaktan çıkarır: [-2, 5, 0, 3] dizisinde 2. indis için çarpım 0 değerini hiç görmez ve sonuç -30 olur.

Bu doğru bir yöntemdir ama aynı işleri tekrarlar. 0. ve 1. indislerin çarpımlarında iki değer dışında her değer ortaktır; yine de hepsini yeniden çarparsınız. n konumun her biri n-1 çarpma işlemi gerektirir; n = 10^4 olduğunda toplamda yaklaşık 10^8 işlem eder. C bunu saniyenin çok küçük bir bölümünde tamamlar, ancak Python, Ruby veya R çok uzun sürer.

Algoritma

n uzunluğunda bir cevap dizisi oluşturun.
Her i indeksi için product değerini 1 olarak ayarlayın.
product değerini, indeksi i olmayan her nums[j] ile çarpın.
product değerini cevabın i indeksine kaydedin.
Cevabı döndürün.

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

Önek ve sonek çarpım dizileri

Sezgi

i dizini için çarpımı ikiye ayır: i değerinden önceki değerler ve sonraki değerler. Bu çarpımlara before[i] ve after[i] adlarını ver. Ardından answer[i] = before[i] × after[i] olur ve nums[i] herhangi bir bölme işlemi yapılmadan dışarıda bırakılır.

Her dizi, komşusundan bir çarpma işlemiyle büyür. before[0], hiçbir değerin çarpımı olan 1’dir ve before[i] = before[i-1] × nums[i-1] olur. Diğer uçtan başlayınca after[n-1] 1’dir ve after[i] = after[i+1] × nums[i+1] olur. [2, 3, 4, 5] için before = [1, 2, 6, 24] ve after = [60, 20, 5, 1] elde edersin; bunları konum konum çarptığında [60, 40, 30, 24] sonucu çıkar.

n adımlı üç geçiş O(n) zaman alır. İki yardımcı dizi O(n) ek bellek gerektirir; sonraki yaklaşım bu gereksinimi ortadan kaldırır.

Algoritma

before'ı soldan doldurun: before[0] = 1, ardından her giriş bir önceki giriş ile bir önceki değerin çarpımıdır.
after'ı sağdan doldurun: after[n-1] = 1, ardından her giriş bir sonraki giriş ile bir sonraki değerin çarpımıdır.
Her indeks için answer[i] değerini before[i] × after[i] olarak ayarlayın.
answer'ı döndürün.

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)]

Yanıtta solda çarpımlar, sağda ise devam eden bir çarpım

Sezgi

Tüm after dizisine bir kerede hiçbir zaman ihtiyacın olmaz. Sağ uçtan ilerlerken, i öğesinin sağındaki değerlerin çarpımı tek bir sayıdır. Bunu right değişkeninde tut ve her adımda bir çarpma işlemiyle güncelle.

Bu yüzden ilk geçişte sol çarpımları doğrudan cevap dizisine yaz. Sağdan yapılan ikinci geçişte answer[i] değerini right ile çarp ve ancak bundan sonra right değerini nums[i] ile çarp. Sıra önemlidir: i indeksinde right değerini kullandığında, henüz nums[i] değerini içermemelidir.

[2, 3, 4, 5] için ilk geçiş sonunda [1, 2, 6, 24] elde edilir. İkinci geçişte 3, 2, 1, 0 indekslerinde right = 1, 5, 20, 60 değerleri kullanılır ve dizi [60, 40, 30, 24] hâline gelir. Süre yine O(n) olur ve döndürdüğün dizi dışında ek bellek tek bir değişkenden ibarettir: O(1).

Algoritma

answer[0] = 1 olarak ayarla, ardından soldan sağa answer[i] = answer[i-1] × nums[i-1] olarak ayarla.
right değerini 1 olarak ayarla.
Son indisten 0'a doğru, answer[i] değerini right ile çarp.
Ardından right değerini nums[i] ile çarp.
answer değerini döndür.

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

Tuzaklar ve uç durumlar

Buradaki hatalar sıfırlardan, ikinci geçişteki iki güncellemenin sırasından ve dizinin sınırlarından kaynaklanıyor.

Toplam çarpımı nums[i] değerine bölmek, bir 0 göründüğünde başarısız olur. [-2, 5, 0, 3] için toplam 0'dır ve 2. indeks için 0'ın 0'a bölünmesi gerekir. Sıfırları saymak bunu düzeltebilir, ancak problem zaten bölme işlemini yasaklıyor.
Kullanmadan önce right değerini nums[i] ile çarpmak, nums[i] değerini kendi çarpımına dahil eder. [2, 3, 4, 5] için son değer 24 yerine 120 olur.
Sol çarpımlara 1 yerine nums[0] ile başlamak. 0. indeksin solunda hiçbir şey bulunmadığından, sol çarpımı boş çarpımdır ve değeri 1'dir; böylece answer[0] yalnızca sağındaki değerlerin çarpımı olur.
Döngü sınırları: sol geçiş nums[i-1] değerini okur, bu yüzden 1. indeksten başlar. Sonek dizisi nums[i+1] değerini okur, bu yüzden n-2. indeksten başlar.
İki sıfır, her yanıtı 0 yapar. Tek bir sıfır, sıfırın kendi indeksindeki yanıt dışındaki tüm yanıtları 0 yapar. Koduna güvenmeden önce her iki durumu da test et.

Sıkça sorulan sorular4

Kendisi Hariç Dizinin Çarpımı'nın zaman karmaşıklığı nedir?

Önek ve sonek çözümü O(n) zamanda çalışır: soldan bir geçiş ve sağdan bir geçiş. Sol taraftaki çarpımlar çıktı dizisinde saklanırken ve tek bir sağ çarpım değeri tutulurken, çıktı dışında O(1) ek alan gerekir. Her indeks için diğer tüm değerleri çarpmak O(n²) zaman alır.

Array Except Self çarpımında bölmeye neden izin verilmiyor?

Toplam çarpımı nums[i] değerine bölmek, dizi sıfır içerdiğinde işe yaramaz; çünkü toplam 0 olur ve sıfırın kendi indeksinde 0'a bölme işlemi gerekir. Bunu çalışır hâle getirmek için sıfırların sayısını tutmak ve özel durumları ele almak gerekir. Bu kural, sıfırları hiçbir özel durum gerektirmeden ele alan önek ve sonek çarpımlarını kullanmaya yönlendirir.

Çıktı dizisi ek alan olarak sayılır mı?

Hayır. Yine de yanıtı döndürmeniz gerekir, bu nedenle olağan kural gereği bu, alan hesabına dahil edilmez. Sol taraftaki çarpımları burada saklamak ve sağ taraftaki çarpımı tek bir değişkende tutmak bu nedenle O(1) ek alan olarak sayılır.

Dizi dışında kalan elemanların çarpımı sıfırları nasıl ele alır?

Önek ve sonek çarpımlarıyla sıfırlar için özel bir duruma gerek yoktur. Sıfırı aşan her sol veya sağ çarpım 0 olur ve sıfırın kendi indeksindeki çarpım sıfırı atlar. İki veya daha fazla sıfır varsa her çarpımda en az bir sıfır bulunur, dolayısıyla tüm yanıtlar 0 olur.

Python

def productExceptSelf(nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [2, 3, 4, 5]

Beklenen

[60, 40, 30, 24]

Product of Array Except Self

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her indeks için diğerlerini çarpın

Önek ve sonek çarpım dizileri

Yanıtta solda çarpımlar, sağda ise devam eden bir çarpım

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler