JZ51：构建乘积数组

方法1：遍历

思路：也就是B[i]=A[0]*A[1]...A[n] 其中不包括A[i];

//-------------复杂度为O(n^2)----------
    public int[] multily1(int[] A){
        if(A.length==0){
            return A;
        }
        int[] B=new int[A.length];
        int result=1;
        for(int i=0;i<A.length;i++){
            for(int j=0;j<A.length;j++){
                if(i==j){
                    continue;
                }
                result=result*A[j];
            }
            B[i]=result;
            result=1;
        }
        return B;
    }

方法2：二维矩阵

       //-----------方法2：---------------------------
    public int[] nultiply2(int[] A){
        // 对A数组i项右侧自下往上累乘 时间复杂度O(n)
        // 将B拆分为A[0] *...* A[i-1]和A[n-1]*...*A[i+1] 两部分
        if(A.length==0){
            return A;
        }
        int[] B=new int[A.length];
        B[0]=1;
        //先计算左下三角形，此时B[0]只有一个元素，设为1
        for(int i=1;i<A.length;i++){
            B[i]=B[i-1]*A[i-1];
        }
        int temp=1;
        //计算右上三角形
        for(int i=A.length-1;i>=0;i--){
            B[i]=B[i]*temp;
            temp=temp*A[i];
        }
        return B;
    }