class Solution {
public:
vector<int> constructArr(vector<int>& a) {
}
};
剑指 Offer 66. 构建乘积数组
给定一个数组 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]。不能使用除法。
示例:
输入: [1,2,3,4,5] 输出: [120,60,40,30,24]
提示：
a.length <= 100000原站题解
python3 解法, 执行用时: 80 ms, 内存消耗: 25.6 MB, 提交时间: 2022-11-13 14:33:26
class Solution:
def constructArr(self, a: List[int]) -> List[int]:
length = len(a)
if length == 0: return []
# L 和 R 分别表示左右两侧的乘积列表
L, R, answer = [0]*length, [0]*length, [0]*length
# L[i] 为索引 i 左侧所有元素的乘积
# 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
L[0] = 1
for i in range(1, length):
L[i] = a[i - 1] * L[i - 1]
# R[i] 为索引 i 右侧所有元素的乘积
# 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
R[length - 1] = 1
for i in reversed(range(length - 1)):
R[i] = a[i + 1] * R[i + 1]
# 对于索引 i，除 a[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
for i in range(length):
answer[i] = L[i] * R[i]
return answer
python3 解法, 执行用时: 60 ms, 内存消耗: 23 MB, 提交时间: 2022-11-13 14:32:57
class Solution:
def constructArr(self, a: List[int]) -> List[int]:
length = len(a)
if length == 0: return []
answer = [0]*length
# answer[i] 表示索引 i 左侧所有元素的乘积
# 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
answer[0] = 1
for i in range(1, length):
answer[i] = a[i - 1] * answer[i - 1]
# R 为右侧所有元素的乘积
# 刚开始右边没有元素，所以 R = 1
R = 1;
for i in reversed(range(length)):
# 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
answer[i] = answer[i] * R
# R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
R *= a[i]
return answer