50. 数组剔除元素后的乘积

描述

给定一个整数数组A。
定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 计算B的时候请不要使用除法。

样例

给出A=[1, 2, 3]，返回 B为[6, 3, 2]

思路

左右分治效率很高，减少了重复计算。result[i] = left[i] * right[i] ，left[i] = A[0] * A[1] *** A[i-1]，right[i] = A[i+1] * A[i+2]*** A[len(A)-1]。将最后的乘积分为两部分求解，首先求得左半部分的值，然后求得右半部分的值。最后将左右两半部分乘起来即为解。

时间复杂度 O(n).
使用了左右两半部分辅助空间，空间复杂度 O(2n).

注意

初值 left[0] = 1. right[A.size()-1] = 1

代码

public class Solution {
    /*
     * @param nums: Given an integers array A
     * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    public List<Long> productExcludeItself(List<Integer> A) {
        List<Long> B = new ArrayList<Long>();
        if (A == null || A.size() == 1){
            long bi = 1;
            B.add(bi);
            return B;
        }
        
        long[] left = new long[A.size()];
        long[] right = new long[A.size()];
        left[0] = 1;
        
        for (int i = 1; i < A.size(); i++){
            left[i] = left[i-1] * A.get(i-1);
        }
        
        right[A.size()-1] = 1;
        for (int i = A.size()-2; i>=0 ; i--){
            right[i] = right[i+1] * A.get(i+1);
        }
        
        for (int i = 0; i < A.size(); i++){
            long res = right[i] * left[i];
            B.add(res);
        }
        
        return B;
    }
}