238. Product of Array Except Self

Leetcode 問題: 238. Product of Array Except Self
Categories:
Tags:

題目

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

傳入整數陣列 nums，回傳一個整數陣列，上面的陣列索引結果是，每個元素除了自己以外，的乘法總和

傳入數字的乘法合保證是 32-bit 整數

必須寫一個演算法，時間複雜度是 O(n)，且沒有使用除法去去求得數字

PS: 除法方式是，計算完整個陣列的乘法合，然後除以索引數字，就可以得到該元素排除自己的乘法合

Example

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

演算法

1. 不使用額外空間去儲存乘法結果

僅使用一個陣列去儲存答案，不額外使用空間儲存答案

2. 從前方 i = 0 計算每個數字的 prefix 前方所有乘法合數字

第一個數字前面沒有 prefix 數字，所以預設為 1，1 乘以任何數不會對任何數做異動

數字陣列 [1,2,3,4] prefix 乘法合

數字 1 2 3 4
prefix 前綴乘法合 1 1 2 6
prefix 運算 1 (無前綴，預設 1) 1 1 * 2 1 * 2 * 3

將這個運算結果紀錄在結果的陣列，然後繼續加上 postfix 後面數字乘法合

2. 從後方 i = length -1 計算每個數字的 postfix 後方所有乘法合數字

最後一個數字後面沒有 postfix 數字，所以預設為 1，1 乘以任何數不會對任何數做異動

數字陣列 [1,2,3,4] postfix 乘法合

數字 1 2 3 4
postfix 後綴乘法合 24 12 4 1
postfix 運算 2 * 3 * 4 3 * 4 4 1 (無後綴，預設 1)
prefix 前綴乘法合 1 1 2 6
prefix 運算 1 (無前綴，預設 1) 1 1 * 2 1 * 2 * 3
prefix 與 postfix 乘法合 24 12 8 6
prefix 與 postfix 運算 1 * 2 * 3 * 4 1 * 3 * 4 1 * 2 * 4 1 * 2 * 3 * 1

最後會發現，直接將 prefix 運算完的乘法合，直接乘以 postfix 的乘法合，就可以獲得最後的答案了 [24,12,8,6]

答案

JavaScript

function productExceptSelf(numsList) {
    // 建立一個乘法的結果陣列
    var numsProductResult = new Array(numsList.length);
    // prefix 總和，第一個數字前面沒有 prefix，預設為 1，1 乘以任何數不會對任何數做異動
    var prefixNumProduct = 1;
    for (var i = 0; i < numsList.length; i++) {
        var currentNumber = numsList[i];
        // 設定目前數字的 prefix 數字「乘法總合」
        numsProductResult[i] = prefixNumProduct;
        // 設定目前數字的乘法總和，給下一個數字當作 prefix 使用
        prefixNumProduct = prefixNumProduct * currentNumber;
    }
    // postfix 總和，最後一個數字後面沒有 postfix，預設為 1，1 乘以任何數不會對任何數做異動
    var postfixNumProduct = 1;
    for (var i = numsList.length - 1; i >= 0; i--) {
        var currentNumber = numsList[i];
        // 設定目前數字的 prefix 與 postfix 的「乘法總合」
        numsProductResult[i] = numsProductResult[i] * postfixNumProduct;
        // 設定目前數字的乘法總和，給下一個數字當作 postfix 使用
        postfixNumProduct = postfixNumProduct * currentNumber;
    }
    return numsProductResult;
}

TypeScript

function productExceptSelf(numsList: number[]): number[] {
    // 建立一個乘法的結果陣列
    let numsProductResult = new Array(numsList.length);

    // prefix 總和，第一個數字前面沒有 prefix，預設為 1，1 乘以任何數不會對任何數做異動
    let prefixNumProduct = 1;

    for (let i = 0; i < numsList.length; i++) {
        let currentNumber = numsList[i];
        // 設定目前數字的 prefix 數字「乘法總合」
        numsProductResult[i] = prefixNumProduct;
        // 設定目前數字的乘法總和，給下一個數字當作 prefix 使用
        prefixNumProduct = prefixNumProduct * currentNumber;
    }

    // postfix 總和，最後一個數字後面沒有 postfix，預設為 1，1 乘以任何數不會對任何數做異動
    let postfixNumProduct = 1;
    for (let i = numsList.length -1; i >=0; i--) {
        let currentNumber = numsList[i];
        // 設定目前數字的 prefix 與 postfix 的「乘法總合」
        numsProductResult[i] = numsProductResult[i] * postfixNumProduct;
        // 設定目前數字的乘法總和，給下一個數字當作 postfix 使用
        postfixNumProduct = postfixNumProduct * currentNumber;
    }

    return numsProductResult;
};

參考資料