【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].

测试用例

1. 功能测试：输入数组包含正数、负数、一个0、多个0。
2. 边界值测试：输入数组的长度为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