构建乘积数组

知识点 数组

描述

给定一个数组 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]（除 A[i] 以外的全部元素的的乘积）。程序中不能使用除法。（注意：规定 B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2]）

对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。

数据范围：1 \le n \le 10 \1≤n≤10  ，数组中元素满足 |val| \le 10 \∣val∣≤10 

        做这道题我只想出了暴力破解法。暴力破解法非常之简单。就是使用双层for循环把每个位置的左右两边的数都乘一遍。时间复杂度，太耗时了。

//暴力破解法
for (int i = 0; i < length; i++) {
    int value = 1;
    for (int j =0; j < i; j++) {
        value *= A[j];
    }
    for (int k =i+1; k < length; k++) {
        value *= A[k];
    }
    B[i] = value;
    return B;
}

        后面看了大神的解题思路，发现太吊炸天了。自己怎么没想到用两个数组把数组中每个数的左边乘积和右边乘积都单独计算和存储下来。感觉还是自己做题的时候不敢想，不敢大胆假设。

        结合大神的解题思路，我自己尝试写了一下，思想是一样的，我写的更好理解，但是比大神的占用多一点空间。

       下面代码思路还是很明了的，处理的时候小心一点临界点就好了。

 int length = A.length;
 //参考了大神的答案，自己尝试也写一遍
 int [] B = new int[length]; // 用来存放A[i]位置处左边所有数的乘积
 int [] C = new int [length]; // 用来存放A[i]位置处右边所有数的乘积
 
 B[0] = 1; //A[0]左边没有数据
 for (int i = 1; i <length; i++) {
     B[i] = B[i - 1] * A[i-1];
 }
 
 C[length - 1] =1;
 for (int i = length -2; i >=0; i--) {
    //C[i]表示A[i]元素右边所有数的乘积
    //所以C[i + 1]表示A[i + 1]元素右边所有数的乘积
    //所以C[i] = C[i + 1] * A[i + 1]
     C[i] = C[i + 1] * A[i + 1]; 
 }
 
 for (int i = 0; i < length; i++) {
     A[i] = B[i] * C[i];
 }
 return A;

参考文章：

CodeSolution/剑指Offer51-构建乘积数组.md at main · Damaer/CodeSolution · GitHub