day7 at Leetcode

238. Product of Array Except Self

最初こう考えたが、remove() は値を消す関数であって、インデックスを消す関数ではなかった。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            numss = nums.remove(i)
            result = 1
            for n in numss:
                result *= n
        return result

remove(i) は「値が i の要素」を消してしまう上に、戻り値が None なので for n in numss がそもそもエラーになる。

次に、元のリストをコピーしてから使えばいいのではと考えたが、tmp = nums はコピーではなく同じリストを指すだけという罠にハマった。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        tmp = nums
        resultlist=[]
        for i in range(len(nums)):
            nums=tmp
            nums.remove(nums[i])
            result = 1
            for n in nums:
                result *= n
        resultlist.append(result)
        return resultlist

tmp = nums はエイリアス（別名）を作るだけなので、nums.remove() すると tmp の中身も一緒に減っていく。ループのたびにリストがどんどん縮んでいき、最終的に IndexError になった。しかも resultlist.append(result) がループの外にあったので、仮に動いても最後の1個しか結果が入らなかった。

修正版:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        resultlist = []
        for i in range(len(nums)):
            excluded = nums[:i] + nums[i+1:]   # コピーではなく「除いた新しいリスト」を毎回作る
            result = 1
            for n in excluded:
                result *= n
            resultlist.append(result)          # ループの中でappend
        return resultlist

nums[:i] + nums[i+1:] で「i番目を除いた新しいリスト」を毎回スライスで作ることで、元の nums を一切破壊せずに済んだ。値の重複があっても安全。

ただし内側の for n in excluded も外側の for i も両方 O(n) なので、全体では O(n²)。この問題は本来 O(n)・割り算なしが条件なので、次は「左からの累積積」「右からの累積積」を別々に持っておく方式に挑戦した。

O(n)への改善
O(n²) 版は各 i ごとにリストを作り直して for で全部掛け直していた（ループの中にループ）ので遅い。「左からの累積積」と「右からの累積積」を別々に持っておいて最後に掛け合わせれば、ループを2回（＋掛け合わせで1回）に減らせる。

インデックス: 0 1 2 3
nums: 1 2 3 4
左からの積(prefix): 1 1 2 6 ← nums[i]より左の積（自分は含まない）
右からの積(suffix): 24 12 4 1 ← nums[i]より右の積（自分は含まない）
answer[i] = prefix[i] * suffix[i]
answer: 24 12 8 6

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix = [1] * n
        suffix = [1] * n

        # 左からの累積積を作る
        for i in range(1, n):
            prefix[i] = prefix[i-1] * nums[i-1]

        # 右からの累積積を作る
        for i in range(n-2, -1, -1):
            suffix[i] = suffix[i+1] * nums[i+1]

        # 掛け合わせる
        return [prefix[i] * suffix[i] for i in range(n)]

前の O(n²) 版は「1個ずつリストを作って全部掛け直す」を n 回繰り返していたのに対して、今回は「左から1周」「右から1周」「掛け合わせで1周」の合計3周（=O(n)）で終わるのがポイント。割り算も使っていない。