怎么在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];
 }
 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中構建一個乘積數組問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。