Pythonで「自分以外の全要素の積」からなるリストを求めるプログラム(除算不使用)

数値のリスト nums が与えられたとき、新しく生成するリストの各インデックス i の要素が、元のリストのうちインデックス i の要素以外のすべての数値の積となるようなリストを求めます。ただし、この問題は除算を使用せずに解く必要があります。

例えば、入力が nums = [2, 3, 4, 5, 6] の場合、出力は [360, 240, 180, 144, 120] となります。

解法のアプローチ

この問題は、「左側からの累積積」と「右側からの累積積」の2つの配列を組み合わせることで、O(n) の時間計算量で効率的に解くことができます。以下の手順に従います。

• nums のサイズが 1 未満の場合は、そのまま nums を返す
• n := nums のサイズ
• left := サイズ n のリスト(初期値はすべて null)
• right := サイズ n のリスト(初期値はすべて null)
• temp := 1
• i を 0 から nums のサイズまで繰り返す:
  • i が 0 の場合:left[i] := temp
  • それ以外の場合:temp := temp × nums[i − 1]、left[i] := temp
• temp := 1 に戻す
• i を nums のサイズ − 1 から 0 まで逆順に繰り返す:
  • i が nums のサイズ − 1 の場合:right[i] := temp
  • それ以外の場合:temp := temp × nums[i + 1]、right[i] := temp
• i を 0 から nums のサイズまで繰り返し、left[i] := left[i] × right[i] とする
• left を返す

仕組みのポイント

left[i] には「インデックス i より前にあるすべての要素の積」が格納され、right[i] には「インデックス i より後ろにあるすべての要素の積」が格納されます。したがって、両者を掛け合わせた left[i] × right[i] が、まさしく「インデックス i の要素を除く全要素の積」となります。除算を一切使わずに目的の結果が得られるのがこの手法の大きな特徴です。

実装例

class Solution:
   def solve(self, nums):
      if len(nums) < 1:
         return nums
      l = len(nums)
      left = [None] * l
      right = [None] * l
      temp = 1
      for i in range(len(nums)):
         if i == 0:
            left[i] = temp
         else:
            temp = temp * nums[i - 1]
            left[i] = temp
      temp = 1
      for i in range(len(nums) - 1, -1, -1):
         if i == len(nums) - 1:
            right[i] = temp
         else:
            temp = temp * nums[i + 1]
            right[i] = temp
      for i in range(len(nums)):
         left[i] = left[i] * right[i]
      return left
ob = Solution()
nums = [2, 3, 4, 5, 6]
print(ob.solve(nums))

入力

[2, 3, 4, 5, 6]

出力

[360, 240, 180, 144, 120]

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。リストを前方向と後方向の2回走査するだけで済むため、単純な二重ループによる O(n²) の素朴な解法と比べて大幅に高速です。