Product of Array Exclude Itself 50

Question

Given an integers array A.

Define B[i] = A[0] ... A[i-1] A[i+1] ... * A[n-1], calculate B WITHOUT divide operation.

Example

For A = [1, 2, 3], return [6, 3, 2].

Solution

有点动态规划的思想。

首先从后往前遍历数组，用f[i]保存i到end所有元素的乘积。

然后从前往后遍历数组，对于当前位i，其值的计算公式为start~i-1的元素的乘积 * f[i]。start~i-1的乘积在i-1位置时已经可以得到。

代码如下：

public class Solution {
    /**
     * @param A: Given an integers array A
     * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
        // write your code
        //DP
        ArrayList<Long> res = new ArrayList<Long>();
        if(A == null || A.size() == 0){
            return res;
        }

        int n = A.size();
        //f[i]:product from i to end
        long[] f = new long[n];
        f[n - 1] = A.get(n - 1);
        for(int i = n - 2; i >= 0; i--){
            f[i] = A.get(i) * f[i + 1];
        }

        //从开头到当前元素之前的元素之积
        long now = 1;
        //从开头到当前元素之积
        long temp = 1;
        for(int i = 0; i < n; i++){
            now = temp;
            if(i + 1 < n){
                res.add(now * f[i + 1]);
            }else{
                res.add(now);
            }
            temp = now * A.get(i);
        }

        return res;
    }
}