题目：数组剔除元素后的乘积

给定一个整数数组A。

定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 计算B的时候请不要使用除法。

您在真实的面试中是否遇到过这个题？ Yes 哪家公司问你的这个题？ Airbnb Alibaba Amazon Apple Baidu Bloomberg Cisco Dropbox Ebay Facebook Google Hulu Intel Linkedin Microsoft NetEase Nvidia Oracle Pinterest Snapchat Tencent Twitter Uber Xiaomi Yahoo Yelp Zenefits 感谢您的反馈 样例

给出A=[1, 2, 3]，返回 B为[6, 3, 2]

标签 Expand 前后遍历 LintCode 版权所有
public class Solution {
    /**
     * @param A: Given an integers array A
     * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
        // write your code
        ArrayList<Long> result = new ArrayList<>();
        for(int i=0;i<A.size();i++){
             Long mul = 1L;
             for(int j=0;j<A.size();j++){
                  if(j!=i){
                       mul = mul*A.get(j);
                  }
             }
             result.add(mul);
        }
       
        return result;
    }
}

时间复杂度为O（n）的AC代码 public class Solution {
    /**
     * @param A: Given an integers array A
     * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
        ArrayList<Long> res = new ArrayList<Long>();
         if (A==null || A.size()==0) return res;
         long[] lProduct = new long[A.size()];
         long[] rProduct = new long[A.size()];
         lProduct[0] = 1;
         for (int i=1; i<A.size(); i++) {
             lProduct[i] = lProduct[i-1]*A.get(i-1);
         }
         rProduct[A.size()-1] = 1;
         for (int j=A.size()-2; j>=0; j--) {
             rProduct[j] = rProduct[j+1]*A.get(j+1);
         }
         for (int k=0; k<A.size(); k++) {
             res.add(lProduct[k] * rProduct[k]);
         }
         return res;
    }
}