Single Number
リスト nums が与えられます。このリストでは、1つの値だけが1回出現し、ほかのすべての値はちょうど2回出現します。1回だけ出現する値を返してください。
関数
- numsinteger-array
- 1つを除き、すべての値が2回ずつ現れるリスト
- 戻り値integer
- 一度だけ現れる値
制約
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- 各値はちょうど2回ずつ現れますが、1つの値だけはちょうど1回しか現れません。
例
- 入力
- nums = [8, 3, 8]
- 出力
- 3
- 説明
- 8は2回、3は1回出現するので、答えは3です。
- 入力
- nums = [5, -2, 7, 5, 7]
- 出力
- -2
- 説明
- 5 と 7 はそれぞれ 2 回現れ、-2 は 1 回だけ現れる唯一の値です。負の答えも、正の答えと同じ方法で求められます。
- 入力
- nums = [42]
- 出力
- 42
- 説明
- 値が1つだけのリストにはペアがまったくないため、その値が答えです。
提出時に隠しテスト+13件
発展問題
1つを除くすべての値が3回ずつ現れるとしたらどうでしょうか？XORだけでは、3回現れる値は相殺されなくなります。それでも、O(n)時間、O(1)の追加メモリで1つだけの値を見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
等しい値のペアをすべて消せるなら、答えだけが残ります。等しい2つの数を何もない状態にする操作はあるでしょうか？
XORには次の性質があります。
x ^ xは0であり、x ^ 0はxです。また、順序に依存しないため、値の2つのコピーは打ち消し合うために隣り合っている必要はありません。0から始まる変数を1つ用意します。numsのすべての値をその変数にXORし、最後にその変数を返します。マップもソートも必要ありません。
解説
相手のいない値を1つ見つけるのは数え上げの問題であり、ハッシュマップを使えば1回の走査ですべての値を数えられます。ただし、メモリが必要です。マップはリストに応じて大きくなります。XORを使えば、そもそも数える必要がありません。値を自分自身とXORすると0になるからです。リスト全体の値をXORすると、すべてのペアが打ち消し合い、1つの変数だけを使って1回の走査で単独の値が残ります。
スキャンして各値を数える
正しいが、最大のテストでは終わらない
考え方
各値を順番に取り出し、リスト全体を調べて、その値が何回出現するか数えます。ペアになっている値は2回として数えます。単独の値は1回なので、出現回数が1の最初の値を返します。
答えの定義から数え方が直接導かれ、カウンター以外の追加メモリも必要ないため、これは正しい方法です。
n 個の値それぞれについて、n 個の値をすべて調べるため、処理に時間がかかります。単独の値が9,999個のリストの末尾にある場合、比較回数は10^8に近くなります。
アルゴリズム
numsの各値を順に処理します。- リスト全体を調べ、その値と等しい値の個数を数えます。
- 個数が 1 なら、その値を返します。
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0ハッシュマップで数える
考え方
値ごとにリストを再走査すると、作業が重複します。代わりに、1回の走査ですべての値を数えましょう。値から個数へのハッシュマップを用意し、各ステップで現在の値の個数に1を加えます。
[5, -2, 7, 5, 7]の場合、最終的にマップは5 → 2、-2 → 1、7 → 2となります。マップを2回目に走査すると、個数が1のエントリーが見つかります。それは-2です。
各値につきマップの更新が1回必要なので、時間計算量はO(n)です。マップには約n/2個のエントリーが格納されるため、追加のメモリ使用量はO(n)です。組み込みのマップがないCでは、値が小さいため、value + 10^4をインデックスとするカウンターの配列が同じ役割を果たします。
アルゴリズム
- 値から出現回数への空のマップを作成します。
numsの各値について、その出現回数に 1 を加えます。- マップを確認し、出現回数が 1 の値を返します。
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XORですべての値を処理する
考え方
XORは2つの数値をビットごとに比較し、異なるビットを1にします。次の3つの性質が成り立ちます。x ^ x = 0、x ^ 0 = x、そして演算の順序は関係ありません。
そこで、0から始まる1つの変数にリスト全体のXORを取ります。演算を並べ替えて、同じ値のペア同士を組み合わせると、各ペアは0になります。残るのは0 ^ singleで、これは単独の値です。[8, 3, 8]の場合：0 ^ 8 = 8、次に8 ^ 3 = 11、次に11 ^ 8 = 3です。
負の数でも同様に機能します。XORは2の補数表現のビットに対して作用し、等しい負の数は同じビットを持つため、他のペアと同じように打ち消し合います。ループは各値を1回読み取り、変数を1つだけ保持します。時間計算量はO(n)、追加メモリはO(1)です。
アルゴリズム
resultを0に設定します。numsの各値について、resultをresult ^ valueに設定します。resultを返します。
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
落とし穴と境界ケース
XOR のループは短いため、間違いは開始位置や、よく使われる別の方法に潜んでいます。
resultをnums[0]に設定してから、インデックス 0 を含むすべての値をループすること。最初の値が XOR で 2 回加算され、打ち消し合ってしまいます。0 から開始するか、インデックス 0 を飛ばしましょう。- ソートして隣り合う要素を 2 つずつ比較し、単独の値が最後の要素になり得ることを忘れること。
[1, 1, 2]には異なるペアが存在せず、答えは残った 2 です。 2 × sum(distinct values) - sum(nums)を使うこと。正しい数値は得られますが、異なる値の集合にはO(n)のメモリが必要です。XOR を使う方法ならこれを避けられます。- XOR が他の出現回数でも機能すると期待すること。XOR は偶数回出現する値を打ち消します。ある値が 3 回出現した場合、1 つが残って答えを狂わせます。
よくある質問4
Single Number の時間計算量はどのくらいですか？
XORによる解法は、各値を一度読み取り、変数を1つだけ保持するため、実行時間はO(n)、追加の領域はO(1)です。ハッシュマップも実行時間はO(n)ですが、O(n)のメモリが必要です。新たに走査して各値を数える方法では、実行時間はO(n²)です。
XOR はなぜ Single Number を解決できるのでしょうか？
数値をそれ自身と XOR すると 0 になり、0 と XOR しても何も変わらず、演算の順序も関係ありません。したがって、リスト全体に XOR を適用すると、各ペアをまとめて 0 にできます。相方のない値だけが残ります。
XOR のテクニックは負の数でも機能しますか？
はい。XORは数値を格納するビットに対して動作し、負の数は2の補数で格納されます。等しい2つの負の数は同じビット列を持つため、正の数と同じように打ち消し合います。[5, -2, 7, 5, 7] の結果は -2 です。
他の値が3回現れる場合は、どう解けばよいでしょうか？
XORはペアを打ち消しますが、3つ組は打ち消さないため、ここではうまくいきません。代わりに、32個のビットそれぞれについて、そのビットが立っている値の数を数えます。3つ組は3の倍数を加えるため、各ビットの個数を3で割った余りが、単独の値のそのビットになります。これでもO(n)時間、O(1)の追加メモリで実行できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def singleNumber(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [8, 3, 8]
期待値
3