首页 > 编程语言 > 详细

构建乘积数组

时间:2018-10-11 18:11:33      阅读:163      评论:0      收藏:0      [点我收藏+]

题目描述

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

对于第一个for循环
第一步:b[0] = 1;
第二步:b[1] = b[0] * a[0] = a[0]
第三步:b[2] = b[1] * a[1] = a[0] * a[1];
第四步:b[3] = b[2] * a[2] = a[0] * a[1] * a[2];
第五步:b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3];
然后对于第二个for循环
第一步
temp *= a[4] = a[4]; 
b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4];
第二步
temp *= a[3] = a[4] * a[3];
b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3];
第三步
temp *= a[2] = a[4] * a[3] * a[2]; 
b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2];
第四步
temp *= a[1] = a[4] * a[3] * a[2] * a[1]; 
b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1];
由此可以看出从b[4]到b[0]均已经得到正确计算。


import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        int length = A.length;
        int[] B = new int[length];
        if (length != 0) {
            B[0] = 1;
            for (int i = 1; i < length; i++) {
                B[i] = B[i - 1] * A[i - 1]; //先计算下三角
            }
            int temp = 1;
            for (int j = length - 2; j >= 0; j--) {
                temp *= A[j + 1]; //计算上三角,注意要j要从length - 2开始,B[length - 1]已经算出来了,不需要再乘以上三角,直接算B[length - 2]
                B[j] *= temp;
            }             
        }
        return B;
    }
}

构建乘积数组

原文:https://www.cnblogs.com/MarkLeeBYR/p/9773723.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!