LintCode题解|Twitter 面试题：Residual Product

题目描述

输入为整数数组 arr，请你返回结果数组 ans，使得 ans[i] 为 arr 中除了 arr[i] 以外的所有数的乘积。

思路点拨

先计算总乘积，再进行除法，时间复杂度 O(n)。

考点分析

简单的热身题，算完总乘积后做除法就行了，做到bugfree即可。

九章参考程序

www.jiuzhang.com/solution/re…

/**
* 本参考程序来自九章算法，由 @斌助教 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，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;
    }
}