[LeetCode] 238. Product of Array Except Self (JS)

[LeetCode] 238. Product of Array Except Self (JS)

題目

給定一個長度為 n 的整數陣列 nums ,其中 n > 1,返回輸出陣列 answer ,其中 answer[i] 等於 nums 中除 nums[i] 之外其餘各元素的乘積。

nums 的任何前綴或後綴的乘積都保證適合 32 位元整數。

題目限制在 O(n) 時間複雜度內完成,且不能使用除法

Example 1:

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

Example 2:

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

Constraints:

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

解題思路

  • 前綴積陣列(Prefix Product Array):計算每個位置 i 左側所有元素的乘積。
  • 後綴積陣列(Suffix Product Array):計算每個位置 i 右側所有元素的乘積。

最終結果中的每個位置 i 的值將是對應位置的前綴積和後綴積的乘積。

前綴積陣列

nums: [2,4,1,3,5]

第一個元素為 2,除去 2 以外,其他元素的乘積恰好是後面四個元素的乘積,而後面四個元素的乘積就是 2 的後綴之積,根據 前綴之積*後綴之積 = 後綴之積 的公式可得出前綴之積為 1

第二個元素是4,前綴之積是 2 * 2 的前綴之積,也就是 1 * 2 = 2

然後是1,前綴之積是 4 * 4 的前綴之積,也就是 1 * 2 * 4 = 8

再來是3,前綴之積是 1 * 1 的前綴之積,也就是 1 * 2 * 4 * 1 = 8

最後是5,前綴之積是 3 * 3 的前綴之積,也就是 1 * 2 * 4 * 1 * 3 = 24

得出的前綴之積陣列為 L: [1,2,8,8,24]

後綴積陣列

後綴積也是同樣的求法,只不過是從陣列後面往前遍歷

nums: [2,4,1,3,5]

最後一位元素是 5,除去 5 以外,其他元素的乘積恰好是前面四個元素的乘積,而前面四個元素的乘積就是 5 的前綴之積,根據 前綴之積*後綴之積 = 前綴之積 的公式可得出後綴之積為 1

第二個元素是3,後綴之積是 5 * 5 的後綴之積,也就是 1 * 5 = 5

然後是1,後綴之積是 3 * 3 的後綴之積,也就是 1 * 5 * 3 = 15

再來是4,後綴之積是 1 * 1 的後綴之積,也就是 1 * 5 * 3 * 1 = 15

最後是2,後綴之積是 4 * 4 的後綴之積,也就是 1 * 5 * 3 * 1 * 4 = 60

得出的後綴之積陣列為 R: [60,15,15,5,1]

求解

nums: [2,4,1,3,5] 得出前綴積陣列為 L: [1,2,8,8,24],後綴積陣列為 R: [60,15,15,5,1]

那麼將前綴積和後綴積相乘就能得到答案,也就是 answer: [60, 30, 120, 40, 24]

  • 時間複雜度:O(n) 3輪循環,其中 n 指的是 input 陣列的長度
  • 空間複雜度:O(n) 2個陣列,使用了前綴積陣列和後綴積陣列去得到答案

進階:空間複雜度O(1)

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

最後題目進階問能否使用空間複雜度 O(1) 完成? (輸出陣列不計入

這代表我們不能用兩個陣列 L, R 來完成。

改進方式是第一輪循環直接使用 answer 來存儲前綴之積,第二輪循環求後綴之積 R 的過程不變,第三輪循環中直接將 answer 的對應元素乘以 R 的對應元素。

nums: [2,4,1,3,5]
answer: [1,2,8,8,24] * R: [60,15,15,5,1]
      : [60, 30, 120, 40, 24]

第一輪循環
1.answer 存儲每個元素的前綴之積
第二輪循環
1.answer 更新為前綴之積和後綴之積的乘積
2.然後更新每個元素的後綴之積 R

如此一來便省了一輪循環並且空間複雜度變為 O(1)

完整程式碼

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    let answer = new Array(nums.length).fill(0)
    // 前綴積
    answer[0] = 1
    for (let i = 1; i < nums.length; i++) {
        answer[i] = answer[i - 1] * nums[i - 1]
    }
    // 後綴積
    let R = 1
    for (let i = nums.length - 1; i >= 0; i--) {        
        answer[i] *= R
        R *= nums[i]
    }
    return answer
};
guest

0 評論
最舊
最新 最多投票
內聯回饋
查看全部評論