题目描述
输入为整数数组 arr，请你返回结果数组 ans，使得 ans[i] 为 arr 中除了 arr[i] 以外的所有数的乘积。
思路点拨
先计算总乘积，再进行除法，时间复杂度 O(n)。
考点分析
简单的热身题，算完总乘积后做除法就行了，做到bugfree即可。
参考程序
http://www.jiuzhang.com/solution/residual-product/
/**
* 本参考程序来自九章算法，由 @斌助教 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/
public class Solution {
/**
* @param arr: The array you should handle
* @return: Return the product
*/
public int[] getProduct(int[] arr) {
// Write your code here
if(arr.length == 1) {
int[] ans = new int[1];
ans[0] = 0;
return ans;
}
int[] pre = new int[arr.length];
int[] suf = new int[arr.length];
int[] ans = new int [arr.length];
pre[0] = arr[0];
for(int i = 1; i < arr.length; i++) {
pre[i] = arr[i] * pre[i - 1];
}
suf[arr.length - 1] = arr[arr.length - 1];
for(int i = arr.length - 2; i >= 0; i--) {
suf[i] = suf[i + 1] * arr[i];
}
ans[0] = suf[1];
ans[arr.length - 1] = pre[arr.length - 2];
for(int i = 1; i <= arr.length - 2; i++) {
ans[i] = pre[i - 1] * suf[i + 1];
}
return ans;
}
}
