目次
解いた問題
leetcode 136. Single Number
非空の整数配列 nums が与えられて、この配列の中では、ある1つの要素だけが1回だけ出現し、その他すべての要素は2回ずつ出現するから、1回だけ出現する要素を見つけてくださいって問題。
さらに、条件として以下を満たす必要がある：
- 線形時間計算量$O(n)$
- 定数空間$O(1)$のみを使用
学び
- やっぱりアルゴリズムは面白い！！！
- 重複消してカウントするのにもハッシュマップは有用
- より空間計算量を減らしたいときは問題文の特性を生かして「ビット演算」を利用する
補足：ハッシュマップとは
キー（key）に対して値（value）を高速に取り出すためのデータ構造。
平均$O(1)$で検索・挿入・削除できる。
ハッシュマップ（HashMap）は：
- key をハッシュ関数で数値に変換（ハッシュ値）
- そのハッシュ値を 配列の添字 として使い
- 対応する位置に value を格納する
という仕組み。
だから高速。
イメージとしては鍵（key）を数字に変換し、その数字を住所（配列の index）として手紙（value）を置いておくイメージ。
→鍵さえ知っておけば手紙を一発で見つけられるってわけ。
Pythonにおいては辞書型dictを使用して実装する。詳しい実装は省くが下記にハッシュマップの実装例があるので見てほしい。
最初に考えた解法
numsの中で1回しか出てこない数値をreturnしてねとのことだったので、ハッシュマップが使えると考えて実装してみた。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
hashmap = {}
for i in nums:
if i not in hashmap:
hashmap[i] = 1
else:
hashmap[i] += 1
filtered = [k for k, v in hashmap.items() if v == 1]
return filtered[0]
一発正解！いえ～～～～い
ただ問題文には「空間計算量を$O(1)$にしてね」という条件がある。
first.pyだと入力の要素数に比例してハッシュマップが増えるため$O(n)$となるのでNG。
とはいえどう改善するかぱっと思いつかなかったのでAIに答えを聞いた。
答え
本問題の最適解は「XOR（排他的論理和）を使った O(n), O(1) 解法」らしいです。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for n in nums:
result ^= n # XOR
return result
うーんわからん。
細かくみていく。
排他的論理和とは
2つのビットが “異なる” ときだけ 1 になる演算のこと。
つまり下記のようになる演算を指す。
^は何か
^はPythonにおけるビット演算子の一つで「排他的論理和」を表す演算子。
こいつは単に数値のXORを取るのではなく、「ビット演算子」なので入力を2進数に変換した後XORを取る。
だから1 ^ 5 → 4のような一見よくわからない答えが出るが、下記のように2進数でビット演算すると理解できる。
1 ^ 5 # 答えは「4」
001 # 2進数の「1」
101 # 2進数の「5」
--- # XOR
100 # 2進数の「4」
他のビット演算子は下記
result ^= nは何をしているか
これはresult = result ^ nと同じことで、resultとnumsの中身のXORを取ってresultに結果を入れているだけ。
Pythonでは^が排他的論理和を表す演算子。
インクリメントa += 1などではなじみがあるが、XORではあまり見ないため初見で何やっているかわからなかった。
結論
この問題では「出てくる数字の回数が1回or2回」と決まっていることが肝になる。
2回出る、すなわち偶数回出る値はXORを取ると完全に0となってしまうからだ。
101 # 10進数の「5」
101 # 10進数の「5」
--- # XOR
000 # 「0」となる
1回出る、すなわち奇数回出る値は打ち消されることがなく、かつ上記のようにほかの数値は勝手に影響がなくなるため、「XORを取り続けると最終的に欲しい値のみが答えに出てくる」という仕組みになっている！！
下記のように途中計算を10進数で見てしまうと何がどうなっているかわからないが、上記の2進数での計算を考えると出力だけ見ればいいことがわかる。
感想
面白い！！！！
こんなところでも数学が活きてくるのか。
いろんな領域の知識が組み合わさってようやく結果に結びつく感覚は結構好きです。
自分の頭の中にある独立した知識が結びついて新しい知識になって、既知が未知になるというか。
AI領域は特にこの感覚が強いのでもっと楽しんでいきたい。