剑指offer题解--①构建乘积数

题目：构建乘积数组

描述：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]*A[i+1]...*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

解题过程:
1.起初，题目都没看懂，-_-~,后面才发现相当于就是把当前位置的数值不乘进去；
2.那就突然就明白了，就开始码，简单的嘛，直接两个for循环就搞定了。

    public int[] multiply(int[] A) {
        if(A.length == 0){
            return new int[0];
        }
        int[] result = new int[A.length];
        for (int i = 0; i < result.length; i++) {
            int temp = 1 ;
            for (int j = 0; j < A.length; j++) {
                if (j != i){
                    if (A[j] == 0){
                        temp = 0;
                        break;
                    }
                    temp *= A[j];
                }
            }
            result[i] = temp;
        }
        return result;
    }

但是这样发现时间复杂度为O(n²)

还可以利用动态规划的思想，把上下两部分的乘积用两个数组保存起来

   public int[] multiply(int[] A) {
        if(A.length == 0){
            return new int[0];
        }
        //利用上下两个三角形计算才做乘机
        int[] result = new int[A.length];
        int [] tempUp = new int[A.length];
        int [] tempDowm = new int[A.length];
        tempDowm[0] = 1;
        for (int i = 1; i < A.length; i++) {
            tempDowm[i] = tempDowm[i - 1] * A[i - 1];
        }
        tempUp[A.length - 1] = 1;
        for (int i = A.length - 2; i >= 0; i--) {
            tempUp[i] = tempUp[i + 1] * A[i +1];
        }
        for (int i = 0; i < A.length; i++) {
            result[i] = tempDowm[i] * tempUp[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {};
        MyNowCoder newCo = new MyNowCoder();
        int[] multiply = newCo.multiply(arr);
        for (int i : multiply) {
            System.out.println(i);
        }
    }