Sword to Offer-66 构建乘积数组 ❀❀

22 May 2020 in Algorithm

• 题目描述：
  给定一个数组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]。

解题思路：

思路1：暴力双重循环，求B[i]时除了下标为i的那个数，其他数直接连乘。

思路2：动态规划： 1、leftMulti记录左边下标为[0~i]数的积，表示A数组前i+1个数的积，rightMulti记录右边下标为[i~n-1]的积，表示A数组后n-i个数的积；
2、所求的B[i] = leftMulti[i-1] * rightMulti[i+1]，即为左边部分的连乘*右边部分的连乘；
3、特殊值，B第一个值为rightMulti[1]，最后一个值为left[n-2]。

解法一、双重循环

AC代码：

// Multiply All Numbers in Array Except Position i

import java.util.ArrayList;

public class Solution {
    public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        if (A==null || A.length==0) {
            return B;
        }
        for (int i=0; i<A.length; i++) {
            B[i] = 1;
            for (int j=0; j<A.length; j++) {
                if (i != j){
                    B[i] *= A[j];
                }
            }
        }
        return B;
    }
}

解法二、动态规划

问题图解：

AC代码：

import java.util.ArrayList;

public class Solution {
    public int[] multiply(int[] A) {
        int n = A.length;
        int[] B = new int[n];
        if (A==null || n==0) {
            return B;
        }
        int[] leftMulti = new int[n];
        int[] rightMulti = new int[n];
        leftMulti[0] = A[0];
        for (int i=1; i<n; i++) {
           leftMulti[i] = leftMulti[i-1] * A[i]; 
        }
        rightMulti[n-1] = A[n-1];
        for (int i = n-2; i>=0; i--) {
            rightMulti[i] = rightMulti[i+1] * A[i];
        }
        B[0] = rightMulti[1];
        B[n-1] = leftMulti[n-2];
        for (int i=1; i<n-1; i++) {
            B[i] = leftMulti[i-1] * rightMulti[i+1];
        }
        return B;
    }
}

补充说明：

• 这里是牛客编码链接