构建乘积数组

题目描述

给定一个数组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]。不能使用除法。

时间限制:1秒 空间限制:32768K

解题思路

1、暴力解题:使用双重循环赋值,时间复杂度为O(n^2)

public class Solution {
    public int[] multiply(int[] A) {
        int[] B=new int[A.length];
        for(int i=0;i

2、前后拆分:将A[0]*A[1]*...*A[i-1]和A[i+1]*...*A[n-1]分为两部分计算,然后相乘,时间复杂度O(n)

M[i]=A[0]*A[1]*...*A[i-1]N[i]=A[i+1]*...*A[n-1],则B[i]=M[i]*N[i]

  • 第一个循环从左到右将M[i]赋值给B[i]:B[i]=M[i]、第二个循环从右到左将N[i]乘进去:B[i]*=N[i]
public class Solution {
    public int[] multiply(int[] A) {
        int[] B=new int[A.length];
        int tmp=1;
        for(int i=0;i=0;i--){
            B[i]*=tmp;
            tmp*=A[i];
        }
        return B;
    }
}

你可能感兴趣的