作者:whisper
链接:https://www.proprogrammar.com/article/850
声明:请尊重原作者的劳动,如需转载请注明出处
给定一个数组 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]
提示:
- 所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
难度:中等;标签:无;编程语言:JAVA
class Solution {
public int[] constructArr(int[] a) {
if(a.length == 0)return a;
int[] pre = new int[a.length + 1], post = new int[a.length];
pre[0] = 1;
post[post.length - 1] = 1;
for(int i = 1; i < a.length; i++)pre[i] = pre[i - 1] * a[i - 1];
for(int i = a.length - 2; i >= 0; i--)post[i] = post[i + 1] * a[i + 1];
for(int i = 0; i < a.length; i++){
a[i] = pre[i] * post[i];
}
return a;
}
}
学过前缀(后缀)和的比较好理解,这里用的是前缀和后缀积,如一个位置i,那么用0~i-1的前缀积乘以i+1~len-1的后缀积就是i位置的结果,可以学一下计算前(后)缀积(和)的方法
class Solution {
public int[] constructArr(int[] a) {
if (Objects.isNull(a) || a.length == 0) {
return new int[]{};
}
int[] res = new int[a.length];
int left = 1;
for (int i = 0; i < res.length; i++) {
res[i] =left;
left *= a[i];
}
int right = 1;
for (int i = res.length - 1; i >= 0; i--) {
res[i] *= right;
right *= a[i];
}
return res;
}
}
这里的优点是用两个变量代替前后缀积两个数组,方法是一样的,但代码比较好
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论