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; } }