https://leetcode.com/problems/product-of-array-except-self/#/description
image.png
分析
- 將某個(gè)元素 左邊所有元素相乘 * 右邊所有元素相乘 返回即可
Python 超時(shí)版
- 16/17 有個(gè)超長(zhǎng)的列表又尼瑪超時(shí)了们衙。惧互。。
- Time O(n^2)
- Space O(n)
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nn = []
for i in range(len(nums)):
nn.append(self.pro(nums, 0, i) * self.pro(nums, i+1, len(nums)))
return nn
def pro(self, nums, start, end):
s = 1
for i in range(start, end):
s *= nums[i]
return s
繼續(xù)分析
- 假設(shè)有一個(gè)列表pro_before = [..pro(nums, 0, i)..]
- 有個(gè)列表pro_after = [...pro(nums, i, len(nums)..]
- 那么本題的解為pro_before[i] * pro_after[i]
- 而上述兩個(gè)列表只需要正向 反向掃描nums即可
- 這樣只有線性?huà)呙?Time O(n)
- 注意這里pro_before * pro_after 所以實(shí)際上都是連乘在里面所以不需要開(kāi)兩個(gè)數(shù)組
- 只需要初始化res為全1的數(shù)組即可
- Space O(n)
image.png
Python
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res = [1] * len(nums)
t = 1
for i in range(len(nums)):
res[i] *= t
t *= nums[i]
t = 1
for i in range(len(nums) - 1, -1, -1):
res[i] *= t
t *= nums[i]
return res
