【Python】自身を除く配列要素の積を除算なしで求める方法

問題の概要

n > 1 を満たす n 個の整数からなる配列 nums があるとします。ここで、output[i] が nums[i] 以外のすべての要素の積と等しくなるような配列 output を求めます。

例えば、入力配列が [1,2,3,4] の場合、出力は [24,12,8,6] となります。重要な制約として、この問題は除算演算子を使用せずに解く必要があります。

解法のアプローチ

この問題は「右側からの累積積」と「左側からの累積積（プレフィックス）」を組み合わせることで効率的に解けます。各位置 i に対して、「左側の要素の積 × 右側の要素の積」を計算すればよいのです。

アルゴリズムの手順

• right_mul：nums と同じサイズの配列を作成し、0 で初期化する
• right_mul の最後の要素に nums の最後の要素を代入する
• i を 1 から nums の長さまでループする：
  right_mul[len(nums) - i - 1] = right_mul[len(nums) - i] * nums[len(nums) - i - 1]
• output：nums と同じサイズの配列を作成し、0 で初期化する
• prefix := 1、index := 0 とする
• index < len(output) - 1 の間、以下を繰り返す：
  ・output[index] = prefix * right_mul[index + 1]
  ・prefix = prefix * nums[index]
  ・index += 1
• output の最後の要素に prefix を代入する
• output を返す

理解を深めるために、以下の実装例を見てみましょう。

実装例

class Solution(object):
    def productExceptSelf(self, nums):
        right_multiply = [0] * len(nums)
        right_multiply[-1] = nums[-1]
        for i in range(1, len(nums)):
            right_multiply[len(nums)-i-1] = right_multiply[len(nums)-i] * nums[len(nums)-i-1]
        output = [0]*len(nums)
        prefix = 1
        current_index = 0
        while current_index < len(output)-1:
            output[current_index] = prefix * right_multiply[current_index+1]
            prefix *= nums[current_index]
            current_index += 1
        output[-1] = prefix
        return output

ob1 = Solution()
print(ob1.productExceptSelf([1,3,5,7,9]))

入力

[1,3,5,7,9]

出力

[945, 315, 189, 135, 105]

計算量の分析

このアルゴリズムは配列を2回走査するだけで済むため、時間計算量は O(n) です。また、出力用の配列を除けば追加のメモリは right_mul のみで、空間計算量も O(n) に抑えられます。除算を使用しないため、ゼロ除算のリスクがなく、浮動小数点誤差の心配もありません。この手法は LeetCode の「Product of Array Except Self」などの定番問題でも広く使われるアプローチです。