Missing Number
0からnまでの範囲にある、互いに異なる整数n個のリストnumsが与えられます。0からnまでの範囲にはn+1個の数があるため、そのうちリストに含まれていない数がちょうど1つあります。その欠けている数を返してください。
関数
- numsinteger-array
- 0からnまでの範囲にある、順不同の相異なるn個の整数
- 戻り値integer
- numsに含まれていない、0からnまでの数値1つ
制約
n == nums.length1 ≤ n ≤ 1040 ≤ nums[i] ≤ n-
numsのすべての値は異なります。
例
- 入力
- nums = [4, 2, 0, 1]
- 出力
- 3
- 説明
- リストには4つの値があるため、範囲は0から4です。0、1、2、4が含まれており、一致するものがない数は3だけです。
- 入力
- nums = [1]
- 出力
- 0
- 説明
- 値が1つの場合、範囲は0と1です。リストには1が含まれているため、0が欠けています。
- 入力
- nums = [0, 1, 2]
- 出力
- 3
- 説明
- 3 未満の数はすべて含まれているため、欠けているのは範囲の上限である 3 そのものです。これはリストのインデックスではないため、上限の扱いには注意が必要です。
提出時に隠しテスト+13件
発展問題
リストがソート済みなら、二分探索を使って O(log n) 時間で欠けている数を見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
リストに入るべき数値は正確にわかっています。
0からnまでのすべての整数です。その範囲全体について計算でき、リストについて計算した同じ数値と比較できる数値はありますか？0からnまでの整数の合計はn(n+1)/2であり、リストの合計は欠けている値の分だけちょうど小さくなります。XORも同じように機能し、値をそれ自身とXORすると0になるため、オーバーフローの心配はありません。累積 XOR を使ってリストを1回走査します。
nから始め、各インデックスiでiとnums[i]の両方を XOR に加えます。2回現れる数字はすべて相殺され、欠けている数字が残ります。
解説
リストに何が含まれているべきかは正確にわかっています。つまり、0 から n までのすべての整数です。それらの数を一つずつ検索する方法でも機能しますが、数ごとに全体を走査することになります。代わりに、範囲全体とリストをそれぞれ合計値か XOR の1つの要約値にまとめ、その2つの差を取れば、欠けている数がわかります。これなら1回の走査で済み、追加のメモリも必要ありません。
すべての候補を確認する
正しいが、最大のテストでは終わらない
考え方
答えは、0からnまでのn+1個の数のうちの1つです。順番に候補を取り上げ、それぞれについてリストを検索します。どの値とも一致しない最初の候補が、欠けている数です。
これは、範囲内の各数はリストに含まれているか、答えであるかのどちらかであり、リストに重複がないため、検索に失敗する候補はちょうど1つだからです。
各候補について最大n個の値を検索する必要があるため、処理に時間がかかります。欠けている数が上限近くにある場合、ほとんどすべての候補を検索することになります。n = 10^4で欠けている数が末尾近くにある場合、比較回数は約5 × 10^7回です。リストのサイズを2倍にすると、処理量は4倍になります。
アルゴリズム
0からnまで、両端を含めてcandidateをループします。numsを走査し、candidateと等しい値を探します。- 走査で見つかった場合は、次の候補に進みます。
- 一致するものがないまま走査が終了した場合は、
candidateを返します。
def missingNumber(nums):
n = len(nums)
for candidate in range(n + 1):
# "in" on a list scans it from the start: O(n) per candidate.
if candidate not in nums:
return candidate
return -1期待される合計から合計を引く
考え方
何も欠けていなければ、リストには0からnまでのすべての数が含まれ、その合計はn(n+1)/2になります。実際のリストは、その全体から1つの数を取り除いたものなので、合計はちょうどその数だけ少なくなります。
[4, 2, 0, 1]の場合、nは4で、範囲全体の合計は4 × 5 / 2 = 10です。リストの合計は7なので、10から7を引くと3になります。
リストを1回走査して合計するため、時間計算量はO(n)で、保持するのは1つの累積合計だけです。ここでは、全体の合計は最大でもおよそ5 × 10^7であり、32ビット整数に収まります。nがはるかに大きい場合、この式は32ビット整数でオーバーフローするため、Java、C、C++、C#、Rustの各バージョンでは、64ビットで計算します。
アルゴリズム
nをnumsの長さとします。- 合計値全体
n(n+1)/2を計算します。 numsのすべての値を合計します。- 合計値全体からリストの合計を引いた値を返します。
def missingNumber(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)インデックスと値の XOR を取る
考え方
XORではペアが打ち消し合います。a ^ aは0、a ^ 0はaとなり、演算の順序は関係ありません。したがって、ある値だけが1回だけ現れ、ほかの数値がすべて2回ずつ現れるような数値の集まりにXORを適用すると、ペアは消え、その値だけが残ります。
問題から、そのような数値の集まりを作ります。インデックス0からnまでと、nums内の値を合わせます。リスト内にある数値は、インデックスとして1回、値として1回現れるため、打ち消し合います。欠けている数値はインデックスとしてしか現れないため、残ります。ループではインデックス0からn-1までを訪れるので、最後の値も含めるため、結果をnから始めます。
[4, 2, 0, 1]の場合：4から始め、次に0と4、1と2、2と0、3と1をXORします。4、2、1、0はすべて打ち消し合い、3が残ります。これは実行中の値1つで1回走査する方法です。また、合計とは異なり、nがすでに使っているビットを超えて値が大きくなることはないため、オーバーフローしません。
アルゴリズム
resultをn（numsの長さ）に設定します。- 各インデックス
iについて、resultとi、さらにnums[i]の排他的論理和を取ります。 resultを返します。
def missingNumber(nums):
# Start with n, the one index the loop below never reaches.
result = len(nums)
for i, value in enumerate(nums):
result ^= i ^ value
return result
落とし穴と境界ケース
間違った答えの多くは、範囲の両端が原因です。
n自体が欠けている可能性を忘れる。[0, 1, 2]では答えは3で、リストのインデックスではありません。XORを使う方法ではnから始める必要があり、最初にnums[i] != iとなる位置を探すソート済み配列の走査では、すべての位置が一致する場合にnを返す必要があります。- 範囲のサイズを間違える。数値は
0からnまでなので、n+1個あり、合計はn(n+1)/2です。(n-1)n/2ではありません。 0が必ず存在すると仮定する。[1]では答えは0で、1から探索を始めるコードでは見つけられません。- 合計を使う方法でのオーバーフロー。32ビット演算では、
n(n+1)の積はnが約46,000を超えるとオーバーフローします。2で割っても間に合いません。また、n(n+1)/2自体も約65,000で収まらなくなります。64ビット演算かXORを使いましょう。
よくある質問4
Missing Number の時間計算量はどれくらいですか？
和を使う解法とXORを使う解法は、各値を1回ずつ読み取り、数値を1つだけ保持するため、どちらも時間計算量は O(n)、追加の空間計算量は O(1) です。候補ごとにリストを検索すると、時間計算量は O(n²) になります。最初にソートして欠けている値を探すと、時間計算量は O(n log n) になります。
なぜ XOR で欠けている数が見つかるのでしょうか？
数値をそれ自身と XOR すると 0 になり、0 と XOR しても何も変わらず、順序も関係ありません。0 から n までのすべてのインデックスとすべての値を XOR すると、リスト内の各数値は 2 回現れて打ち消し合います。欠けている数値はインデックスとして 1 回だけ現れるため、それが結果になります。
合計の公式と XOR のどちらを使うべきでしょうか？
どちらも1回の走査で済み、必要なメモリは一定です。合計のほうが説明しやすいですが、32ビット演算では、nが約46,000を超えると積n(n+1)がオーバーフローするため、64ビット演算が必要です。XORはオーバーフローしません。Python、Rubyなどの整数に上限がない言語では、この違いはなくなります。
ハッシュセットを使って Missing Number を解けますか？
はい。すべての値を集合に入れ、0からnまで確認して、集合に含まれていない最初の数を返します。これは時間計算量がO(n)ですが、追加メモリをO(n)使用します。合計値やXORを使う方法では、この追加メモリを避けられます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def missingNumber(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [4, 2, 0, 1]
期待値
3