面试题66. 构建乘积数组
2021-01-25 13:15
标签：形式 class 试题 就会 idt 迭代 mic ret str 题目： 解答: 思路描述： 计算除 A[i] 以外所有元素的乘积，如果我们使用两层遍历就会重复计算很多次乘法， 其实就相当于求 A[i] 左边所有元素的乘积之和和右边所有元素的乘积 如果我们每次只考虑一边的乘积的话，比如left[i]代表i左侧的乘积，那么left[i + 1] = A[i] * left[i] right[i] 代表 i 右侧的乘积，那么 right[i - 1] = A[i] * right[i] 其实我们没必要新开辟 left、right 数组，直接在结果数组中计算就好。 而上面的递推式写成迭代形式就好了。 面试题66. 构建乘积数组 标签：形式 class 试题 就会 idt 迭代 mic ret str 原文地址：https://www.cnblogs.com/ocpc/p/12860486.html
1 class Solution {
2 public:
3 vectorint> constructArr(vectorint>& a)
4 {
5 int n = a.size();
6 vectorint> ret(n, 1);
7
8 int left = 1;
9 for (int i = 0; i )
10 {
11 ret[i] = left;
12 left = left * a[i];
13 }
14
15 int right = 1;
16 for (int i = n-1; i >= 0; i --)
17 {
18 ret[i] *= right;
19 right *= a[i];
20 }
21 return ret;
22 }
23 };
上一篇：冒泡排序