題目
給定一個長度為 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]
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
};