Product of Array Except Self
整数の配列 nums が与えられます。同じ長さの配列 answer を返してください。ここで、answer[i] は、インデックス i にある要素を除く nums のすべての要素の積です。O(n) 時間で、除算を使わずに実行してください。
関数
- numsinteger-array
- 少なくとも2つの要素を持つ整数の配列
- 戻り値integer-array
- インデックス i の値が、nums[i] を除くすべての要素の積である配列
制約
2 ≤ nums.length ≤ 104-30 ≤ nums[i] ≤ 30-
nums内のすべてのゼロ以外の値の積は32ビット符号付き整数に収まるため、途中で計算する積もすべて収まります。
例
- 入力
- nums = [2, 3, 4, 5]
- 出力
- [60, 40, 30, 24]
- 説明
- 2を除くと3 × 4 × 5 = 60となり、5を除くと2 × 3 × 4 = 24となります。中央の2つも同じように計算できます。2 × 4 × 5 = 40、2 × 3 × 5 = 30です。
- 入力
- nums = [-2, 5, 0, 3]
- 出力
- [0, 0, -30, 0]
- 説明
- 0を含む積はすべて0です。インデックス2の積だけが0を含まず、-2 × 5 × 3 = -30です。
- 入力
- nums = [0, 4, 0, -1]
- 出力
- [0, 0, 0, 0]
- 説明
- ゼロが2つある場合、どの積にも必ず少なくとも1つはゼロが含まれるため、答えのすべての値は0です。
提出時に隠しテスト+14件
発展問題
O(1) の追加領域だけを使用できますか？返す配列は除きます。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各インデックスについて他のすべての値を掛け合わせる方法は機能しますが、値が10,000個ある場合、約1億回の乗算が必要になり、そのほとんどが重複します。インデックス
iの積とインデックスi + 1の積には、何が共通していますか？nums[i]以外のすべては、その左側の値と右側の値に分かれます。すべての接頭辞とすべての接尾辞の積がわかっていれば、それぞれの答えは1回の掛け算で求められます。各インデックスより前の値の積を使い、1から始めて、答えの配列を左から埋めます。次に、右から走査し、インデックスより後の値の積を1つ累積します。まずその積を答えに掛けてから、
nums[i]を掛けます。
解説
nums[i]以外のすべての値の積は、左側の値の積と右側の値の積を掛け合わせたものです。全体の積をnums[i]で割る方法のほうが短く見えますが、ここでは許可されておらず、全体の積が0になる場合はゼロがあると正しく動作しません。接頭辞積と接尾辞積を使えば、2回の走査ですべての左側と右側の積を求められるため、答えを求める時間計算量はO(n)です。出力配列に左側の積を格納し、1つの変数で右側の積を保持すれば、ほかの配列は必要ありません。
各インデックスについて、他の値を掛け合わせる
正しいが、最大のテストでは終わらない
考え方
定義に従います。各インデックス i について、積を 1 から始め、インデックス j が i ではないすべての nums[j] を掛け合わせます。あとから割って取り除くのではなく、そのインデックスを飛ばすことで、0があっても問題になりません。[-2, 5, 0, 3] では、インデックス2の積は0を参照せず、-30になります。
これは正しい方法ですが、同じ計算を繰り返します。インデックス0とインデックス1の積は、2つの値を除いてすべて共通しているのに、それらをまたすべて掛け合わせています。n個の位置それぞれに n-1 回の乗算が必要で、n = 10^4 のとき合計で約 10^8 回になります。Cならほんの一瞬で終わりますが、Python、Ruby、Rでは時間がかかりすぎます。
アルゴリズム
- 長さ n の答えの配列を作成します。
- 各インデックス
iについて、productを 1 に設定します。 - インデックス
jがiではないすべてのnums[j]をproductに掛けます。 - 答えのインデックス
iにproductを格納します。 - 答えを返します。
def productExceptSelf(nums):
n = len(nums)
answer = []
for i in range(n):
product = 1
for j in range(n):
if j != i:
product *= nums[j]
answer.append(product)
return answer接頭辞積と接尾辞積の配列
考え方
インデックス i に対する積を2つに分けます。i より前の値の積と、後の値の積です。それぞれを before[i] と after[i] と呼びます。すると、answer[i] = before[i] × after[i] となり、除算を使わずに nums[i] を除外できます。
各配列は、隣の要素に1回乗算して求めます。before[0] は値がない場合の積である1で、before[i] = before[i-1] × nums[i-1] です。反対側からは、after[n-1] が1で、after[i] = after[i+1] × nums[i+1] です。[2, 3, 4, 5] の場合、before = [1, 2, 6, 24] と after = [60, 20, 5, 1] になり、各位置の値同士を掛けると [60, 40, 30, 24] になります。
n ステップの処理を3回行うため、時間計算量は O(n) です。補助配列2つで O(n) の追加メモリが必要ですが、次の方法ではこれをなくします。
アルゴリズム
beforeを左から埋めます。before[0] = 1とし、その後は各要素を直前の要素と直前の値の積にします。afterを右から埋めます。after[n-1] = 1とし、その後は各要素を次の要素と次の値の積にします。- すべてのインデックスについて、
answer[i]をbefore[i] × after[i]に設定します。 answerを返します。
def productExceptSelf(nums):
n = len(nums)
# before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
before = [1] * n
after = [1] * n
for i in range(1, n):
before[i] = before[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
after[i] = after[i + 1] * nums[i + 1]
return [before[i] * after[i] for i in range(n)]答えの左側の積、右側で実行中の積
考え方
after 配列全体を一度に持つ必要はありません。右端から順に処理すると、i の右側にある値の積は1つの数になります。これを変数 right に保持し、各ステップで1回掛け算して更新します。
まず1回目の走査で、左側の積をそのまま答えの配列に書き込みます。2回目の走査では右から進み、answer[i] に right を掛け、その後で right に nums[i] を掛けます。順序が重要です。インデックス i で right を使うとき、まだ nums[i] を含んでいてはいけません。
[2, 3, 4, 5] の場合、1回目の走査後は [1, 2, 6, 24] になります。2回目の走査では、インデックス 3、2、1、0 で right にそれぞれ 1、5、20、60 を使い、配列は [60, 40, 30, 24] になります。時間計算量は引き続き O(n) で、返す配列に加えて必要な追加メモリは変数1つ分、つまり O(1) です。
アルゴリズム
answer[0] = 1に設定し、その後左から右へanswer[i] = answer[i-1] × nums[i-1]に設定します。rightを1に設定します。- 最後のインデックスから0まで逆順に、
answer[i]にrightを掛けます。 - 次に、
rightにnums[i]を掛けます。 answerを返します。
def productExceptSelf(nums):
n = len(nums)
# Pass 1: answer[i] = product of everything left of i
answer = [1] * n
for i in range(1, n):
answer[i] = answer[i - 1] * nums[i - 1]
# Pass 2: multiply in the product of everything right of i
right = 1
for i in range(n - 1, -1, -1):
answer[i] *= right
right *= nums[i]
return answer
落とし穴と境界ケース
ここでのバグは、0、2回目の走査における2つの更新の順序、そして配列の端が原因です。
- 合計の積を
nums[i]で割る方法は、0が現れると失敗します。[-2, 5, 0, 3]の場合、合計は0になり、インデックス2では0を0で割る必要が生じます。0の個数を数えれば対処できますが、そもそも問題の条件で除算は禁止されています。 - 使用する前に
rightにnums[i]を掛けると、nums[i]自身がその積に含まれてしまいます。[2, 3, 4, 5]の場合、最後の値は24ではなく120になります。 - 左側の積を1ではなく
nums[0]から始めること。インデックス0の左側には何もないため、左側の積は空積である1です。この場合、answer[0]は右側の値だけの積になります。 - ループの範囲に注意してください。左側の走査では
nums[i-1]を読み取るため、インデックス1から始めます。サフィックス配列ではnums[i+1]を読み取るため、n-2から始めます。 - 0が2つあると、すべての答えが0になります。0が1つの場合は、その0自身のインデックスの答えを除き、すべての答えが0になります。コードを信頼する前に、この両方のケースをテストしてください。
よくある質問4
Product of Array Except Self の時間計算量はどれくらいですか？
接頭辞と接尾辞を使う解法は、左から1回、右から1回走査するため、O(n) 時間で実行できます。左側の積を出力配列に格納し、右側の積を1つだけ累積していけば、出力以外に必要な追加領域は O(1) です。各インデックスについて他のすべての値を掛け合わせる方法では、O(n²) 時間がかかります。
Product of Array Except Self ではなぜ除算が許可されていないのですか？
配列にゼロが含まれている場合、全体の積は0になり、ゼロ自身のインデックスでは0で割る必要があるため、全体の積をnums[i]で割る方法はうまくいきません。これを機能させるには、ゼロの個数を数え、特別なケースを設ける必要があります。このルールから、ゼロも特別なケースなしで処理できる、接頭辞と接尾辞の積を使う方法が導かれます。
出力配列は追加の領域として数えられますか？
いいえ。いずれにしても答えを返す必要があるため、通常の慣例ではそれを空間計算量に含めません。したがって、左側の積をその中に格納し、右側の積を1つの変数に保持する場合、追加の空間計算量は O(1) です。
Product of Array Except Self はゼロをどのように処理しますか？
prefix と suffix の積を使えば、ゼロを特別扱いする必要はありません。ゼロを越えて計算される左側または右側の積は 0 になり、ゼロ自身のインデックスに対する積ではそのゼロをスキップします。ゼロが 2 つ以上ある場合、すべての積にゼロが含まれるため、すべての答えは 0 になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def productExceptSelf(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [2, 3, 4, 5]
期待値
[60, 40, 30, 24]