JZ66構建乘積陣列
描述
給定一個陣列 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]（除 A[i] 以外的全部元素的的乘積），程式中不能使用除法，（注意：規定 B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2]）
對于 A 長度為 1 的情況，B 無意義，故而無法構建，用例中不包括這種情況，
方法1
思路
矩陣中由對角線1將其分成了上三角和下三角，我們先看下三角，如果我們累乘的時候，B[1]是在B[0]的基礎上乘了新增的一個A[0]，B[2]是在B[1]的基礎上乘了新增的一個A[1]，那我們可以遍歷陣列的程序中不斷將陣列B的前一個數與陣列A的前一個數相乘就得到了下三角中陣列B的當前數，
代碼
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];;
}
int temp = 1;
for (int i = A.length - 1; i >= 0; i--) {
B[i] *= temp;
temp *= A[i];
}
return B;
方法2
思路
陣列 B[i] = A[0]A[1]...A[i-1]A[i+1]...A[n-1]，即除去 A[i] 的所有值相乘
可以將 A[i] 設為1，再用 for 回圈將 A 中所有值相乘
臨時變數 temp 先存盤 A[i] 的值，然后再賦回來，
代碼
package esay.JZ66構建乘積陣列;
import java.util.ArrayList;
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];;
}
int temp = 1;
for (int i = A.length - 1; i >= 0; i--) {
B[i] *= temp;
temp *= A[i];
}
return B;*/
//方法二
int[] B = new int[A.length];
int temp = 0;
for (int i = 0; i < A.length; i++) {
temp = A[i];
A[i] = 1;
B[i] = 1;
for (int j = 0; j < A.length; j++) {
B[i] *= A[j];
}
A[i] =temp;
}
return B;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/534068.html
標籤：Java