NeetCodeのSolutionを書いていく

#

Products of Array Except Self

#

問題概要

#

整数の配列numsが与えられます。 整数の配列を返します。その整数はnums[i]以外の数字の累積です。 それぞれの積は32bitを超えないことが保証されます。

割り算を使わずにO(n)で解けますか？

配列数は2以上1000以下 整数は-20以上20以下

計算時間はO(n)、メモリーはO(n)を目指す。

例

#

Input: nums = [1,2,4,6] Output: [48,24,12,8]

Input: nums = [-1,0,1,2,3] Output: [0,-6,0,0,0]

メモ

#

問題を読みながら、全て掛け合わせておいて、自分自身で割った数を出そうと思っていたら。。。 問題の最後に「割り算を使わずに出来るか？」という記載が！ 割り算を使わずにO(n)で処理を完了するには・・・？

わからんから答え見ちゃった。 前からの掛け算の結果(prefix)と、後ろからの掛け算(suffix)の結果をi番目の配列に保存しておいて、 配列i番目の結果はprefix[i-1] x suffix[i+1]で計算できる！ 更にメモリ使用量をO(1)にできる解法も紹介されている。 とりあえずシンプルな方で実装してみた。

インデックスの指定がむずい！ 理解できん・・・テストが通るまで色々試すという。知能不足🧠

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

        for i in range(1, num, 1):
            prefix[i] = prefix[i - 1] * nums[i - 1]

        for i in range(num - 2, -1, -1):
            suffix[i] = suffix[i + 1] * nums[i + 1]

        for i in range(num):
            res[i] = prefix[i] * suffix[i]

        return res