Java構建乘積數組的方法

更新時間：2019年03月04日 08:26:43 作者：雨幕下的稻田

這篇文章主要為大家詳細介紹了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 + " ");
 }

}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: