[LeetCode] 238. Product of Array Except Self

轉自LeetCode

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

<Solution>
因為題目有說不能使用除法，所以不能把整個 array 先乘起來，再除以自己來找到答案

且要求時間複雜度為 O(n)

想法如下

• 總共歷遍兩次，第一次求在自己之前的所有乘積。第二次求在自己之後的所有乘積

• 最後再將兩個乘積再相乘，來得到答案

code如下(參考資料)

題目也進一步要求，空間複雜度能不能變成 O(1)

所以可以優化一下之前的 code

• 不需要用到兩個 array 來分別存乘積，直接使用 ans 這個 array 來運算

• 在求自己之後的所有乘積時，多用一個變數來幫忙記錄所有乘積

code 如下


Java

Kotlin