Lintcode: Product of Array Exclude Itself

王朝学院·作者佚名  2016-05-28
窄屏简体版  字體: 小  |  中  |  大  |  超大  

Lintcode: PRoduct of Array Exclude ItselfGiven an integers array A.Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B without divide Operation.ExampleFor A=[1, 2, 3], B is [6, 3, 2]

非常典型的Forward-Backward Traversal方法:

但是第一次做的时候还是忽略了一些问题:比如A.size()==1时,答案应该是空[]

1 public class Solution { 2 /** 3 * @param A: Given an integers array A 4 * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1] 5 */ 6 public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) { 7 // write your code 8 ArrayList<Long> res = new ArrayList<Long>(); 9 if (A==null || A.size()==0 || A.size()==1) return res;10 long[] lProduct = new long[A.size()];11 long[] rProduct = new long[A.size()];12 lProduct[0] = 1;13 for (int i=1; i<A.size(); i++) {14 lProduct[i] = lProduct[i-1]*A.get(i-1);15 }16 rProduct[A.size()-1] = 1;17 for (int j=A.size()-2; j>=0; j--) {18 rProduct[j] = rProduct[j+1]*A.get(j+1);19 }20 for (int k=0; k<A.size(); k++) {21 res.add(lProduct[k] * rProduct[k]);22 }23 return res;24 }25 }

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航