Product of array exclude itself

給一個 array A，求出另一個 array B, B[i] = A[0] .... *A[i-1] * A[i+1] .... *A[n]，自己的位置不乘

暴力法就是用 double loop 去算乘積，遇到 i = j 時就不乘，這樣的時間複雜度是 O (n^2)

public List<Long> productExcludeItself(List<Integer> nums) {
    List<Long> results = new ArrayList<>();
    if (nums == null || nums.size() == 0) {
        return results;
    } else if (nums.size() == 1) {
        results.add(1L);
        return results;
    }

    for (int i=0; i<nums.size(); i++) {
        Long product = 1L;
        for (int j=0; j<nums.size(); j++) {
            if (i != j) {
                product = product*Long.valueOf(nums.get(j));
            }
        }
        results.add(product);
    }
    return results;
}

有更好的方法嗎? 有的

我們可以先算出由前往後的除了自己的乘積，然後算出由後往前的除了自己的乘積，

然後在相乘，就可以得出除了自己的乘積

public List<Long> productExcludeItself(List<Integer> nums) {
    List<Long> results = new ArrayList<>();
    if (nums == null || nums.size() == 0) {
        return results;
    }

    Long[] before = new Long[nums.size()];
    Long[] after = new Long[nums.size()];
    before[0] = 1L;

    Long product = before[0];
    for (int i=1; i<nums.size(); i++) {
        before[i] = product*Long.valueOf(nums.get(i-1));
        product = before[i];
    }

    after[nums.size()-1] = 1L;
    product = 1L;
    for (int i=nums.size()-2; i>=0; i--) {
        after[i] = product*Long.valueOf(nums.get(i+1));
        product = after[i];
    }

    for (int i=0; i<nums.size(); i++) {
        results.add(before[i]*after[i]);
    }

    return results;
}

還可對上面進行優化，可以將迴圈降為兩個即可，並且 results 就用 array，回傳時再轉型速度會快很多

迴圈進行優化的步驟為:

首先看一下第一個迴圈我們是把結果放到 before, 再來是把第二迴圈的結果放到 after, 互相的乘積放到 results

那其實可以將 before 的結果直接放到 results, after 的當前乘積(第二迴圈的 after[i]) 就用一個變數紀錄，

然後最後放進 results 時，要跟 results[i] 算乘積

for (int i=nums.size()-2; i>=0; i--) {
    product *= nums.get(i+1);    //由後往前的乘積
    result[i] = results[i] * product;    //由前往後的乘積 * 由後往前的乘積
}

如此可以少了一個迴圈以及 before, after 變數

 public List<Long> productExcludeItself(List<Integer> nums) {
    Long[] results = new Long[nums.size()];
    if (nums == null || nums.size() == 0) {
        return new ArrayList<>(Arrays.asList(results));
    }
    results[0] = 1L;
    Long product = 1L;
    for (int i=1; i<nums.size(); i++) {
        product *= Long.valueOf(nums.get(i-1));
        results[i] = product;
    }
    product = 1L;
    for (int i=nums.size()-2; i>=0; i--) {
        product *= Long.valueOf(nums.get(i+1));
        results[i] = results[i]*product;
    }
    return new ArrayList<>(Arrays.asList(results));
}

邊界條件 result[0] = 1 是為了讓第一個迴圈算乘積時不是 null