剑指offer面试题66：构建乘积数组（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],不能使用除法。

测试用例：

1、功能测试：输入的数组包含正数、负数、0 ；

2、负面测试：输入的数组为空或者长度小于2；

方法一：直接连乘 n-1 个数字得到 B[ i ]，时间复杂度为 O（n ）。

方法二：将数组分为两部分分别构建，时间复杂度为 O（n）。

思路：从头到尾构建数组的前半部分 0 ～ i - 1，从尾到头构建数组的后半部分 i + 1～ n - 1，然后再将两部分数组合起来。

public class test_sixty_six {
 public int[] Multiply(int[] A){
  if(A == null || A.length < 2){
   return null;
  }
  
  //构建一个新数组
  int[] result = new int[A.length];   
  result[0] = 1;   //初始化数组第一个元素为0
  
  //从头到尾构建数组的前半部分 0 —— i-1
  for(int i=1; i < A.length; i++){
   result[i] = result[i-1] * A[i-1];
  }
  
  int temp = 1;
  //从尾到头构建数组的后半部分 i+1 —— n-1
  for(int i = A.length-2; i >= 0; i--){
   temp = temp * A[i+1];
   result[i] = result[i] * temp;
  }
  return result;
 }
}