您好,登录后才能下订单哦!
怎么在Java中构建一个乘积数组?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
具体内容如下
给定一个数组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]。
不能使用除法。
解法一
暴力法,这是本能就能想到的解决办法。
public static int[] multiply(int[] array) { if (array == null) { return null; } int len = array.length; if (len == 0) { return null; } int[] result = new int[len]; for (int i = 0; i < len; i++) { int multiply = 1; for (int j = 0; j < len; j++) { if (j != i) { multiply *= array[j]; } } result[i] = multiply; } return result; }
解法二
从中可以看出通过数组A计算数组B的时候,红色部分不参与乘积的计算,以红色部分做分割,可以看错是红色左边部分的乘积与红色右边部分乘积的乘积
所以此时先根据数组A把对应左边部分的乘积和右边部分的乘积分别计算出来得到两个新的数组,即LEFT和RIGHT
这样可以得到公式:B[i]=LEFT[i]*RIGHT[i],如下所示
对于B[0],因为没有左边部分,可以认为是1*RIGHT[0]
如果B[n-1],没有右边部分,所以认为是LEFT[n-1]*1
以下是代码实现
public static int[] multiply2(int[] array) { if (array == null) { return null; } int len = array.length; if (len == 0) { return null; } int[] left = new int[len]; int[] right = new int[len]; int[] result = new int[len]; // 数组B中第一个数字没有左边部分,所以左边乘积数组第一个数字是1 left[0] = 1; // 计算B[i]对应的在A中的左边部分的乘积,数组A从前向后计算 for (int i = 1; i < len; i++) { // 因为要B[i]不需要计算A[i],所以左边部分的乘积计算其实需要的是A中对应下标i的上一个下标及之前的数字 left[i] = left[i - 1] * array[i - 1]; } // 数组B中最后一个数字没有右边部分,所以右边乘积数组的最后一个数字是1 right[len - 1] = 1; // 计算B[i]对应的在A中的右边部分的乘积,数组A从后向前计算,这样才可以一次遍历完 // 因为计算可以用到上一次的结果,即上一次的结果*本次下标的值 for (int i = len - 1; i > 0 ; i--) { // 因为要B[i]不需要计算A[i],所以右边部分的乘积计算其实需要的是A中对应下标i的下一个下标及之后的数字 right[i - 1] = right[i] * array[i]; } for (int i = 0; i < len; i++) { result[i] = left[i] * right[i]; } return result; } public static void main(String[] args) { int[] array = {1, 2, 3, 4}; int[] result = multiply2(array); for (Integer i : result) { System.out.print(i + " "); } }
关于怎么在Java中构建一个乘积数组问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注亿速云行业资讯频道了解更多相关知识。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。