Java构建乘积数组的方法

Java构建乘积数组的方法

本文实例为大家分享了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];

}

rcnOXDhJQQeturn 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 + " ");

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。