JZ51 构建乘积数组

时间:2020-9-9 作者:admin


题目描述

给定一个数组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];)
对于A长度为1的情况,B无意义,故而无法构建,因此该情况不会存在。

思路

  • 读题,理解数组B的规律,发现B[ i ]即i的位置A[i]不存在。也可以理解为1。
  • 不能使用除法。即不能使用这个方法B[i] = A[1] * A[2] * … * A[n-1] / A[1]

画图可发现,类似矩阵的上下三角

不规则图形可以拆分为规则图形计算面积,本题也可以试试
JZ51 构建乘积数组

代码


public class Solution {
    public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        B[0] = 1;
        //下三角
        for (int i = 1; i < A.length; i++) {
            B[i] = B[i-1] * A[i-1];//利用相邻B数组元素的相似性,避免重复计算,同时避免了再次使用for循环
        }
        int temp = 1;
        //上三角
        for (int i = A.length-2; i >= 0  ; i--) {
            temp = temp * A[i+1];
            B[i] = B[i] * temp;
        }
        return B;
    }
}

JZ51 构建乘积数组

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。