剑指 Offer 66. 构建乘积数组
2021-05-04 22:27
标签：inf length 暴力 alt lock 数组 示例 i++ 大量 给定一个数组 示例: 暴力解法，两层循环，直接求解，但是会涉及到大量的重复计算，最后超出时间限制 因为不能使用除法，因此只能将表格分割成上三角和下三角进行计算，对角线的元素值置一，如图所示： 算法流程： 初始化：数组 B ，其中 B[0]=1 ；辅助变量 temp=1 ； 参考作者：jyd 剑指 Offer 66. 构建乘积数组 标签：inf length 暴力 alt lock 数组 示例 i++ 大量 原文地址：https://www.cnblogs.com/gcurry/p/13194178.html剑指 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,2,3,4,5]
输出: [120,60,40,30,24]
思路：
计算 \(B[i]\) 的 下三角 各元素的乘积，直接乘入 B[i] ；
计算$ B[i] $的 上三角 各元素的乘积，记为 temp ，并乘入 B[i] ；
返回 $B $。
代码
class Solution {
public int[] constructArr(int[] a) {
// int len = a.length;
// int[] ans = new int[len];
// for (int i = 0; i = 0; i--) {
temp *= a[i + 1];
ans[i] *= temp;
}
return ans;
}
}
文章标题：剑指 Offer 66. 构建乘积数组
文章链接：http://soscw.com/index.php/essay/82453.html