238. Product of Array Except Self

Question 238

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

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

Example:

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

Note: Please solve it without division and in O(n).

Answer

v1. multiply two lists (70.66%)

1. 產生兩種 list 分別是由右累乘到左以及左累乘到右 input => [a,b,c,d]

   由右累乘 => [1,d,cd,cdb,cdba]

   由左累乘 => [1,a,ab,abc,abcd]

2. 將兩條 list 相乘 [cdb*1 ,cd*a ,d*ab ,1*abc]

v2. multiply two times (84.95%)

1. 初始化 output list 使其皆為 1

2. 於第一個迴圈將由左至右累乘的數字存進 output list 中 其第一個值為 1 (預設)

3. 於第二個迴圈將由左至右累乘的數字乘進原本的 output list 中

v1

class Solution:
    # @param {integer[]} nums
    # @return {integer[]}
    def productExceptSelf(self, nums):
        
        # count len of nums[]
        n = len(nums)
        
        output = []
        left2right=[]
        right2left=[]
        tmpnumL = 1
        tmpnumR = 1
        
        # multiply left to right and right to left
        for i in range(0,n):
            left2right.append(tmpnumL)
            tmpnumL = tmpnumL * nums[i]
            
            right2left.append(tmpnumR)
            tmpnumR = tmpnumR * nums[(n-1)-i]
            

        # multiply each
        for i in range(0,n):
            output.append( right2left[(n-1)-i] * left2right[i] )
        
        return output

v2

class Solution:
    # @param {integer[]} nums
    # @return {integer[]}
    def productExceptSelf(self, nums):
        
        # count len of nums[]
        n = len(nums)
        
        output = [1] * n
        tmpnumL = 1
        tmpnumR = 1
        
        # multiply left to right
        for i in range(0,n-1):
            tmpnumL = tmpnumL * nums[i]
            output[i+1] = tmpnumL
            
        # multiply right to left
        for i in range((n-1),0,-1):
            tmpnumR = tmpnumR * nums[i]
            output[i-1] *= tmpnumR 
        
        return output