[leetcode/lintcode 題解] 國内大廠面試高頻題： 數組除了自身的乘積

描述

給定n個整數的數組nums，其中n> 1，傳回一個數組輸出，使得output [i]等于nums的所有除了nums [i]的元素的乘積。

在沒有除和O(n)時間内解決

線上評測位址：

領扣題庫官網

樣例1
輸入: [1,2,3,4]
輸出: [24,12,8,6]
解釋:
2*3*4=24
1*3*4=12
1*2*4=8
1*2*3=6           

樣例2
輸入: [2,3,8]
輸出: [24,16,6]
解釋:
3*8=24
2*8=16
2*3=6           

解題思路

如果暴力計算每個位置的答案值的話，時間會達到O(N^2)。

如果先将所有數乘起來，每個位置除以目前的數，有可能會整型溢出。

觀察可以發現，每個數其實就是它前面部分的積乘以後面部分的積。所有字首的積，通過一次周遊即可算出來，字尾也是一樣。我們可以邊乘邊算字首積，同時将他乘在結果數組上，這樣達到了O(1)的額外空間，同時不用到除法。

代碼思路

1. 令result為一個全是1的數組。
2. 令字首積prefixProduct等于1，字尾積postfixProduct等于1。
3. 正序周遊數組nums，第i個位置先将結果乘上prefixProduct，再将prefixProduct乘上nums[i]。
4. 逆序周遊數組nums，第i個位置先将結果乘上postfixProduct，再将postfixProduct乘上nums[i]。
5. 傳回result。

複雜度分析

設數組長度為N。

時間複雜度

• 周遊兩次數組，時間複雜度為O(N)。

空間複雜度

• 隻需額外O(1)的時間，記錄字首積和字尾積。

源代碼

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: the product of all the elements of nums except nums[i].
     */
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        int prefixProduct = 1, postfixProduct = 1;
        
        for (int i = 0; i < result.length; i++) {
            result[i] = 1;
        }
        
        // 将第 i 個位置乘上前 i - 1 個數的積
        for (int i = 0; i < result.length; i++) {
            result[i] *= prefixProduct;
            prefixProduct *= nums[i];
        }
        
        // 将第 i 個位置乘上後面數的積
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] *= postfixProduct;
            postfixProduct *= nums[i];
        }
        
        return result;
    }
}           

更多題解參考：

九章官網solution