网站演示程序,青岛公司网站建设价格低,贵州有网站的企业,家用电脑做网站教程给定一个数组 A[0,1,…,n-1]#xff0c;请构建一个数组 B[0,1,…,n-1]#xff0c;其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]A[0]A[1]…A[i-1]A[i1]…A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5] 输出: [120,60,40,30,24]
提示#xff1a;
所有…给定一个数组 A[0,1,…,n-1]请构建一个数组 B[0,1,…,n-1]其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]A[0]×A[1]×…×A[i-1]×A[i1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5] 输出: [120,60,40,30,24]
提示
所有元素乘积之和不会溢出 32 位整数 a.length 100000
解题思路
维护两个数组一个是正向累乘的数组pos[i]表示A[1]* A[2] * …A[i]的值另一个是逆向累乘的数组neg[i]表示A[i]* A[i1] *…A[n-1]的值因此B[i]pos[i-1]*neg[i1]A[0]×A[1]×…×A[i-1]×A[i1]×…×A[n-1]
代码
class Solution {public int[] constructArr(int[] a) {int na.length;if (n1) return a;int[] pos new int[n],negnew int[n],resnew int[n];pos[0]a[0];neg[n-1]a[n-1];for (int i1;in;i)pos[i]a[i]*pos[i-1];for (int in-2;i0;i--)neg[i]a[i]*neg[i1];res[0]neg[1];res[n-1]pos[n-2];for (int i1;in-1;i)res[i]pos[i-1]*neg[i1];return res;}
}
