题目

给定一个数组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];)
对于A长度为1的情况,B无意义,故而无法构建,因此该情况不会存在。

答案

import java.util.ArrayList;
public class Solution {
        public int[] multiply(int[] A) {
            //定义左右数组
        int left[] = new int[A.length];
        int right[] = new int[A.length];
            //定义结果数组
        int B[] = new int[A.length];
            //由于左数组的第一个位置没有,所以是1
        left[0] = 1;
            //右数组的末尾没有数字,所以是1
        right[A.length-1] = 1;
            //让左数组的第2个位置为A数组的首个数字,方便后续重复累乘运算
        left[1] = A[0];
            //让右侧数组的倒数第二个位置为A数组的倒数第一个数字,方便后续重复累乘运算
        right[A.length-2] = A[A.length-1];
            //循环累乘,得到左数组
        for (int i = 1; i < A.length-1; i++) {
            left[i+1] = left[i]*A[i];
        }
            //循环累乘,得到右数组
        for (int i = A.length-2; i>0; i--) {
           right[i-1] = right[i]*A[i];
        }
            //左右数组乘积即是B数组
        for (int i = 0; i < B.length; i++) {
            B[i] = left[i]*right[i];
        }
        return B;
    }
}

题解

这道题不允许用除法,导致稍微费劲了点。

具体思路是这样的
B[i] = A数组除了I以外的其他乘积,那么根据i位置,分成左数组和右数组两个数组。

唯一的难点就是要设计好这两个数组是如何赋值的,左数组left[0]是1,接下来left[i]就是A数组累乘到A[i-1].

相对应的右数组也是一样,只不过他是反过来的,右数组Right[A.length-1]=1,跟左数组一样右数组的末尾也取不到,然后就是从倒数第二个位置依次为右数组赋值Right[A.lengt-2] = A[A.length-1];

赋值结束之后就可以左右相乘给B数组赋值啦


醉后不知天在水,满船清梦压星河