# **Leetcode筆記(Product of Array Except Self)**
:::info
:information_source: 題目 : Product of Array Except Self, 類型 : arrays , 等級 : medium
日期 : 2023/02/17，2023/05/02，2023/06/26，2023/10/11，2024/10/02
:::
### 嘗試
錯誤想法，我先把全部的值先乘起來，但若遇到list中有零的話，總product即會為零
```python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
product = 1
for val in nums:
product = val * product
record = list()
for i, val in enumerate(nums):
product1 = product / val
record.insert(i, product1)
```
2023/05/02
```python
for i, n in enumerate(reversed(nums)):
# 若nums = [1,2,3,4]
# 印出來的會是0 4 /// 1 3 /// 2 2 /// 3 1 ///
# i 還是會從0開始
# 用兩個array
# 對一個數字來說 一個array儲存其前面所有數字的乘積
# 另一個array儲存其後面的所有數字的乘積
# 兩個array相乘 即是答案
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
prefix = [1] * len(nums)
postfix = [1] * len(nums)
res = [1] * len(nums)
temp_pre = 1
for i, n in enumerate(nums):
prefix[i] = temp_pre
temp_pre = temp_pre * n
temp_post = 1
for i, n in enumerate(reversed(nums)):
# 要修正 因為i還是從0開始
postfix[len(nums) - 1 - i] = temp_post
temp_post = temp_post * n
for i in range(len(nums)):
res[i] = postfix[i] * prefix[i]
return res
```
2023/06/26
把左邊和右邊兩個array乘起來
```python
for i, c in enumerate(nums[::-1]):
回傳的c會是倒著的，但是i會是從0~len(nums) - 1的正常輸出
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
prefix = [1] * len(nums)
postfix = [1] * len(nums)
# nums = [1,2,3,4]
# prefix = [1, 1, 2, 6]
# postfix = [24, 12, 4, 1]
# ans = [24, 12, 8, 6]
tempPre = 1
for i, c in enumerate(nums):
prefix[i] = tempPre
tempPre *= c
tempPost = 1
for i, c in enumerate(nums[::-1]):
postfix[len(nums) - i - 1] = tempPost
tempPost *= c
res = [1] * len(nums)
for i in range(len(nums)):
res[i] = prefix[i] * postfix[i]
return res
```
2023/10/11
酷喔，竟然自己做出來了
```python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
tmp = nums[0]
for i in range(1, len(nums)):
res[i] = tmp * res[i]
tmp = tmp * nums[i]
tmp = nums[-1]
for i in range(len(nums) - 2, -1, -1):
res[i] = tmp * res[i]
tmp = tmp * nums[i]
return res
```
2024/10/02
```python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
prefix, suffix, res = [1] * n, [1] * n, [1] * n
for i in range(1, n):
prefix[i] = nums[i - 1] * prefix[i - 1]
for i in range(n - 2, -1, -1):
suffix[i] = nums[i + 1] * suffix[i + 1]
for i in range(n):
res[i] = prefix[i] * suffix[i]
return res
```
---
### **優化**
postfix和prefix去略過待計算值，空間複雜度O(n)，因為沒用到額外記憶體，時間複雜度O(n)
```python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
prefix = 1
output = [1] * len(nums)
# ex. nums = [1,2,3,4]
for i in range(len(nums)): # i = 0, 1, 2, 3
output[i] = prefix # 1, 1, 2, 6
prefix = prefix * nums[i] # 1, 2, 6
postfix = 1
for i in reversed(range(len(nums))): # i = 3, 2, 1, 0
output[i] = output[i] * postfix # postfix = 1, 4, 12, 24 output = 6, 8, 12, 24
postfix = postfix * nums[i] # 4, 12, 24
return output
```
---
**:warning: 錯誤語法**
:::warning
:::
**:thumbsup:學習**
:::success
range(5) -> 為0, 1, 2, 3, 4
創規定長度的空list -> [1] * len(nums)
reversed(range(5)) -> 4 3 2 1 0
range(4,-1,-1) -> 4 3 2 1 0
:::
**思路**
**講解連結**
https://www.youtube.com/watch?v=bNvIQI2wAjk
Provided by. NeetCode
###### tags: `arrays` `leetcode` `medium`
Sign in with Wallet
Connect another wallet