【LeetCode】Product of Array Except Self 解法【python】

leetcode.com

これはかなり考えたけどO(N)かつ除算なしという制限をクリアする解放が思い付かずにいた。 solutionをちらっと見たら図が載っていてそれでなるほど、となった（ソースと解説は読んでいない）。

ある１次配列について、自分以外の要素を乗算した配列を返す、という問題。図にするとこんな感じ↓

ハイフン以外の要素をかける。

除算していいなら、全てを掛け合わせたあとでループして各要素を除算すればOKだがこれは禁止。 各要素について、各要素を除いた数を乗算というブルートフォースが考えられるがO(N)という制限があるので禁止。

で、よくみると、ハイフンを境に、左と右で数字が分かれている。 なので、左の乗算と右の乗算をそれぞれ計算して最後に各要素で掛け話せればO(N)で実現できる。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        length = len(nums)
        l = [1] * (length-1)
        r = [1] * (length-1)
        
        l[0] = nums[0]
        r[0] = nums[-1] 
        
        rnums = nums[::-1]
        
        for i in range(1, len(nums)-1):
            l[i] = nums[i]*l[i-1]
            r[i] = rnums[i]*r[i-1]
            
        return [lv*rv for lv, rv in zip([1]+l, r[::-1]+[1])]
        

処理速度は全体的にみると少し遅いけど、solutionに書かれているものよりは速い。

dicussに書かれていた解法(120ms)は↓

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        if not nums: return False
        
        arr = [1] * len(nums)
        pi = pj = 1

        for i in range(len(nums)):
            j = -1-i

            arr[i]*=pi; arr[j]*=pj
            pi *= nums[i]; pj *= nums[j]        
                    
        return arr