乘积数组"/>
【剑指 Offer 题解】66.构建乘积数组
题目描述
给定一个数组A[0, 1, …, n-1],请构建一个数组B[0, 1, …, n-1],其中B中的元素B[i] =A[0]×A[1]×… ×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
思路
1、若使用可以使用除法,B[i] = 总乘积 / A[i]
2、若暴力解决,连乘后时间复杂度为 O(N^2) ,效率过低
3、B[i] = A[i] 左边连乘 × A[i]右边连乘 = C[i] × D[i]
4、任务分解,计算 C[i] = A[0]×A[1]×… ×A[i-1]
int[] C = new int[n];
int temp = 1;
for (int i = 0; i < n; i++) {C[i] = temp;temp = temp * A[i];
}
5、计算 D[i] = A[i+1]×…×A[n-1]
int[] D = new int[n];
int temp = 1;
for (int i = n-1; i >= 0; i--) {D[i] = temp;temp = temp * A[i];
}
6、计算B[i] = C[i] × D[i]
int[] C = new int[n];
int temp = 1;
for (int i = 0; i < n; i++) {C[i] = temp;temp = temp * A[i];
}
int[] D = new int[n];
temp = 1;
for (int i = n-1; i >= 0; i--) {D[i] = temp;temp = temp * A[i];
}
for (int i = 0; i < n; i++) {B[i] = C[i] * D[i];
}
至此,问题解决。
优化
但观察代码发现,循环计算B[i]时,并未对D[i]修改,是否可以直接在第二个循环中,计算出B[i]呢。
int[] C = new int[n];
int temp = 1;
for (int i = 0; i < n; i++) {C[i] = temp;temp = temp * A[i];
}
temp = 1;
for (int i = n-1; i >= 0; i--) {//D[i] = temp;//B[i] = C[i] * D[i];B[i] = C[i] * temp;temp = temp * A[i];
}
再观察,发现C[i]分配空间只是为了存储前面的乘积,是否也可以直接将值存储在B[i]中。
int temp = 1;
for (int i = 0; i < n; i++) {B[i] = temp;temp = temp * A[i];
}
temp = 1;
for (int i = n-1; i >= 0; i--) {B[i] = B[i] * temp;temp = temp * A[i];
}
至此,问题完美解决。
更多推荐
【剑指 Offer 题解】66.构建乘积数组
发布评论