238. Product of Array Except Self

Leetcode

https://leetcode.com/problems/product-of-array-except-self/description/

題目

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.

Example 1:

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

Example 2:

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

解答

• 方法一

如果可以用除法的話，屬於 easy 題，解法是直接遍歷矩陣兩次，需要注意的是

1. 如果原本矩陣中元素 = 0 的大於 2 個的話，全部回傳值都會是 0

2. 如果原本矩陣中元素 = 0 的等於 1 個的話，除了等於 0 的那個元素其他的回傳值都是 0

var productExceptSelf = function(nums) {
    let total = 1;
    let zeroCount = 0;
    const result = [];

    for(let i=0; i<nums.length; i++) {
        if (nums[i] !== 0) {
            total *= nums[i];
            result[i] = i;
        } else {
            // 用 '0' 代表這個元素是 0
            result[i] = '0';
            zeroCount++;
        }
    }

    // 如果 0 大於兩個的話，回傳的所有元素都會是 0
    if (zeroCount > 1) {
        return result.map(r => 0);
    }

    for(let i=0; i<nums.length; i++) {
        if (result[i] === '0') {
            result[i] = total;
        } else {
            if (zeroCount > 0) {
                // 0 有一個，所以怎麼乘都是 0
                result[i] = 0;
            } else {
                result[i] = total / nums[i];
            }
        }
    }

    return result;
};

Runtime: 97 ms Beats 32.09% of users with JavaScript

Memory: 59.97 MB Beats 48.63% of users with JavaScript

• 方法二

題目規定不能使用除法，那麼要怎麼才能求出除了自己之外乘起來的結果呢？

有一個特殊的思考方向是 某個元素要求的答案 = 左邊所有元素的乘積 * 右邊所有元素的乘積

所以方法就是

1. 從左往右遍歷一次求得 左邊所有元素的乘積

2. 從右往左遍歷一次求得 右邊所有元素的乘積

3. 最後將元素左邊的乘積 * 右邊的乘積即為答案

var productExceptSelf = function (nums) {
    const l2r = [];
    const r2l = [];
    const result = [];
    let total = 1;

    for (let i = 0; i < nums.length; i++) {
        total *= nums[i];
        l2r[i] = total;
    }

    total = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        total *= nums[i];
        r2l[i] = total;

        if (i === 0) {
            result[i] = r2l[i + 1]
        } else if (i === nums.length - 1) {
            result[i] = l2r[i - 1]
        } else {
            result[i] = l2r[i - 1] * r2l[i + 1];
        }
    }

    return result;
};

範例：[1, 2, 3, 4]

l2r = [1, 2, 6, 24]

r2l = [24, 24, 12, 4]

所以以第二個元素 2 來看，結果就會是 l2r[0] * r2l[2] = 1 * 12 = 12

Runtime: 98 ms Beats 29.31% of users with JavaScript

Memory: 66.08 MB Beats 5.14% of users with JavaScript

• 方法三

方法二中的 l2r 是由左往右遍歷，r2l 是由右往左遍歷，不會互相影響，所以我們可以用同一個 result 矩陣來儲存方法二中的 l2r 及 r2r 的結果，以達到空間上的優化

var productExceptSelf = function (nums) {
    const result = [];
    let total = 1;

    for (let i = 0; i < nums.length; i++) {
        // 因為 result[i] 是前面所有元素的乘積，所以這裡先賦值 result[i]
        result[i] = total;
        total *= nums[i];
    }

    total = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        result[i] *= total;
        total *= nums[i];
    }

    return result;
};

Runtime: 80 ms Beats 85.04% of users with JavaScript

Memory: 61.21 MB Beats 30.36% of users with JavaScript

參考資料

【LeetCode】Product Of Array Except Self - 拿空間換時間 - 陣列、前綴和 - 都會阿嬤都會阿嬤

[LeetCode] 238. Product of Array Except Self 除本身之外的数组之积 - Grandyang - 博客园www.cnblogs.com