《剑指offer》-构建乘积数组

/*
 * 给定一个数组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](不包含第i项)。不能使用除法。
 */
public class Multiply {
 //算法一：复杂度O(n^2)
 public int[] multiply(int[] A) {
  if(A.length <= 0) return A;
  
  int[] B = new int[A.length];  
  for(int i = 0;i < B.length; i++) {
   B[i] = 1;
   for(int j = 0;j < A.length; j++) {
    if(j != i) {
     B[i] = B[i] * A[j];
    }
   }
  }
  
  return B;
 }
 
 /*算法二：复杂度O(n)
  * B(0): 1    A(1)   A(2)   ... A(n-1)
  * B(1): A(0)  1     A(2)   ...  A(n-1)
  * B(2): A(0)  A(1)   1   ...    A(n-1)
  *  .
  *  .
  * B(n-1): A(0) A(1)   A(2)   ...    1
  */
 public int[] multiply2(int[] A) {
  if(A.length <= 0) return A;
  
  int[] B = new int[A.length]; 
  int[] temp = new int[A.length];
  int[] temp2 = new int[A.length];
  
  //计算下三角
  temp[0] = 1;
  for(int i = 1;i < temp.length; i++) {
   temp[i] = temp[i - 1] * A[i - 1];
  }
  
  //计算上三角
  temp2[temp2.length - 1] = 1;
  for(int i = temp2.length - 2;i >= 0; i--) {
   temp2[i] = temp2[i + 1] * A[i + 1];
  }
  
  //合成B
  for(int i = 0;i < B.length; i++) {
   B[i] = temp[i] * temp2[i];
  }
  
  return B;
 }
 
 public static void main(String[] args) {
  int[] A = {1,2,3};
  int[] B = new Multiply().multiply2(A);
  
  for(int i : B) {
   System.out.print(i + " ");
  }
 }
}