【劍指Offer學習】【面試題52:構建乘積陣列】

【劍指Offer學習】【面試題52:構建乘積陣列】

題目:給定一個陣列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[]={1,2,3}求B[]
B[0]=A[1]×A[2]=2×3=6
B[1]=A[0]×A[2]=1×3=3
B[2]=A[0]×A[1]=1×2=2

1.B[0]初始化為1,從下標i=1開始,先求出C[i]的值並放入B[i],即B[i]=C[i]=C[i-1]×A[i-1],所以B[1]=B[1-1]×A[1-1]=B[0]×A[0]=1×1=1,i

2.B[2]=B[2-1]×A[2-1]=B[1]×A[1]=1×2=2,i 超出長度停止迴圈

3.C[i]計算完畢求D[i],設定一個臨時變數temp初始化為1

4.從後往前變數陣列,LengthA=3初始化i=LengthA-2=1,結束條件為i>=0

5.第一次迴圈,temp=temp×A[i 1]=1×A[2]=3,計算出A中最後一個元素的值放入temp,temp相當於D[i]的值

6.因為之前的B[i]=C[i],所以讓B[i]×D[i]就是要儲存的結果,即B[i]=B[1]=B[1]×temp=1×3=3,i–=0

7.計算B[i]=B[0],temp上一步中的值是A[2],在這次迴圈中temp=temp×A[0 1]=A[2]×A[1]=3×2=6

8.B[i]=B[0]=B0]×temp=1×6=6,i–<0迴圈結束

所以B陣列為{6,3,2}

程式碼實現

import java.util.Arrays;
public class Test52 {
public static double[] multiply(double[] data) {
if (data == null || data.length < 2) {
return null;
}
double[] result = new double[data.length];
// result[0]取1
result[0] = 1;
for (int i = 1; i < data.length; i  ) {
// 第一步每個result[i]都等於於data[0]*data[1]...data[i-1]
// 當i=n-1時,此時result[n-1]的結果已經計算出來了【A】
result[i] = result[i -1] * data[i - 1];
}
// tmp儲存data[n-1]*data[n-2]...data[i 1]的結果
double tmp = 1;
// 第二步求data[n-1]*data[n-2]...data[i 1]
// 【A】result[n-1]的結果已經計算出來,所以從data.length-2開始操作
for (int i = data.length - 2; i >= 0; i--) {
tmp *= data[i   1];
result[i] *= tmp;
}
return result;
}
public static void main(String[] args) {
double[] array1 = {1, 2, 3, 4, 5};
System.out.println(Arrays.toString(multiply(array1))); // double expected[] = {120, 60, 40, 30, 24};
double[] array2 = {1, 2, 0, 4, 5};
System.out.println(Arrays.toString(multiply(array2))); // double expected[] = {0, 0, 40, 0, 0};
double[] array3 = {1, 2, 0, 4, 0};
System.out.println(Arrays.toString(multiply(array3))); // double expected[] = {0, 0, 0, 0, 0};
double[] array4 = {1, -2, 3, -4, 5};
System.out.println(Arrays.toString(multiply(array4))); // double expected[] = {120, -60, 40, -30, 24};
double[] array5 = {1, -2};
System.out.println(Arrays.toString(multiply(array5))); // double expected[] = {-2, 1};
}
}

執行結果

這裡寫圖片描述