文章目录
- 题目描述
- 思路分析
- 完整代码
题目描述
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
思路分析
将所有的数都乘起来得到一个总乘积，然后求第i位就直接除以i就行了，不过可惜了题目要求不能使用除法。
对于i位的数来讲，其值等于0到i-1的乘积，乘以 i+1到末尾的乘积。看下图。
所以建立两个数组，一个left，一个right，分别存储每个位置的左边乘积和右边乘积(不包含该位置)
比如示例: [1,2,3,4,5]
则其left = [1, 1，2, 6, 24]
right = [120 , 60 , 40 , 30 , 24]
在设置一个存答案的数组res，自然有 :res[i] = left [i] * right[i]
完整代码
class Solution:
def constructArr(self, a: List[int]) -> List[int]:
res = [1] * len(a)
left = [1] * len(a)
right = [1] * len(a)
# 当前元素左边的乘积
for i in range(1,len(a)):
left[i] = left[i-1] * a[i-1]
# 当前元素右边的乘积
for i in range(len(a)-2,-1,-1):
right[i] = right[i+1] * a[i+1]
# 逐个遍历每个位置的左右乘积的乘积就是我们要的答案
for i in range(len(a)):
res[i] = left[i]*right[i]
return res
```