Product of Array Except Self: bölme kullanmadan, her indeks için diğer tüm elemanların çarpımını O(n) zamanda hesaplayın.
Cevap
Her indeks için cevap = solundaki elemanların çarpımı x sağındaki elemanların çarpımı. Önce soldan prefix çarpımlarını, sonra sağdan suffix çarpımlarını tek bir çıktı dizisinde biriktiririz.
Neden bölme yok?
Toplam çarpımı alıp nums[i]'ye bölmek ilk akla gelendir ama dizide 0 varsa çöker; mülakatçı da bölmeyi açıkça yasaklar.
def product_except_self(nums):
n = len(nums)
res = [1] * n
prefix = 1
for i in range(n): # res[i] = sol taraftaki çarpım
res[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1): # sağ taraftaki çarpımla çarp
res[i] *= suffix
suffix *= nums[i]
return res
print(product_except_self([1, 2, 3, 4])) # [24, 12, 8, 6]Adım adım [1,2,3,4]
| i | prefix (sol) | suffix (sağ) | sonuç |
|---|---|---|---|
| 0 | 1 | 24 | 24 |
| 1 | 1 | 12 | 12 |
| 2 | 2 | 4 | 8 |
| 3 | 6 | 1 | 6 |
Karmaşıklık
- Zaman:
O(n)(iki geçiş). - Ek bellek: çıktı dizisi sayılmazsa
O(1).
İlgili Algoritmalar & Veri Yapıları soruları
- Binary search'ün zaman karmaşıklığı nedir ve neden?
- Two Sum: toplamı hedefe eşit olan iki elemanın indekslerini bulun.
- Bir parantez dizisinin geçerli olup olmadığını kontrol edin: "({[]})"
- Tek yönlü bağlı listeyi ters çevirin.
- BFS ve DFS arasındaki fark nedir? Hangisini ne zaman kullanırsınız?
- get ve put işlemleri O(1) olan bir LRU Cache tasarlayın.
Bu konuda başka bir soru biliyor musun?
Mülakatta karşılaştığın soruları ekle, onaylandıktan sonra yayına alınsın.