面试题66 构建乘积数组

问题描述

给定一个数组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[i]的乘积数组的计算矩阵,举例来说,第一个元素是1*A[1..n-1],下标是从0开始的,B[4]是A[0..3]*1*A[5..n-1],我们就思考,1是矩阵的对角线,分出了上下两个矩阵,那么我们可不可以分别用两个数组来表示上三角和下三角呢?

假设有c[n]表示下三角,那么它的计算公式是从前向后递推
$$
c[i] = c[i-1]*A[i-1],c[0]=1
$$
那么后面d[n]也可以表示出来,是从后往前进行递推的
$$
d[i] = d[i+1] * A[ i+1],d[0]=1
$$
根据这个,我们就可以知道,在任意下标,都有
$$
b[i] = c[i] * d[i]
$$

编码

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        int[] c = new int[A.length];
        int[] d = new int[A.length];
        c[0] = 1;
        d[A.length-1] = 1;
        for(int i = 1;i<A.length;i++){
            c[i] = c[i-1] * A[i-1];
        }
        for(int i = A.length-2;i>=0;i--){
            d[i] = d[i+1] * A[i+1];
        }
        int[] b = new int[A.length];
        for(int i = 0 ;i<A.length;i++){
            b[i] = c[i] * d[i];
        }
        return b;
    }
}
# 字符串 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×