【Offer】[66] 【构建乘积数组】

题目描述
思路分析
测试用例
Java代码
代码链接

题目描述

　　给定一个数组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[i]=A[0]xA[]...xA[i-1]xA[i+1]...x A[n-1]看成A[0]xA[1]x...xA[i-1]和A[i+1]...xA[n -2]xA[n-1 ]两部分的乘积。因此，
数组B可以用一个矩阵来创建。在图中，B[i]为矩阵中第i行所有元素的乘积。

定义C[i]=A[0]xA[1]...xA[i-1], D[i]=A[i+1]x...xA[n-2]xA[n-1]。
C[i]可以用自上而下的顺序计算出来，即C[i]=C[i-1]xA[i-1]。类似的，D[i]
也可以用自下而上的顺序计算出来，即D[i]=D[i+1]xA[i+1].

测试用例

功能测试：输入数组包含正数、负数、一个0、多个0。
边界值测试：输入数组的长度为0。

Java代码

public class Offer066 {

    public static void main(String[] args) {

        test1();

        test2();

        test3();

    }

     public static int[] multiply(int[] A) {

        return Solution1(A);

    }

    private static int[] Solution1(int[] A) {

        if(A==null || A.length<2)

            return null;

        int[] B=new int[A.length];

        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-2;i>=0;i--){

            temp*=A[i+1];

            B[i]*=temp;

        }

        return B;

    }

    private static void test1() {

    }

    private static void test2() {

    }

    private static void test3() {

    }

}

代码链接

剑指Offer代码-Java

巴特西