题目链接

题目描述

给定一个数组 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中存放的是，数组A中除了相同索引位置处其他元素的累乘

从左往右，B中存放的是，索引之前元素的累积，拿变量product来保存累乘值，即B[i] = A[0] A[1] A[2] … A[i-1]，这样走到最后，第一个元素先用product代替，最后一个元素是正确的，不用再动弹。

从右往左，上一步B[i]中存放的元素与索引处之后的元素累乘

示例

输入：
[1,2,3,4,5]
输出：
[120,60,40,30,24]

代码

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        if(A.length==0 || A==null){
            return null;
        }
        int n  = A.length;
        int[] B = new int[n];
        /*从左往右累乘 */
        for(int i=0,product=1; i<n;i++){
            B[i] = product;
            product *= A[i]; // 将product赋值给B[i] 后，再去乘A[i],保证B[i]≠A[i]
        }
        /*从右往左累乘 */
        for(int i=n-1,product=1; i>=0;i--){
            B[i] *= product;
            product *= A[i];
        }
        return B;
    }
}