【hashmap/set】重複判定は1行で終わる

目次

解いた問題
学び
最初に考えた解法
正解
最速別解
感想

解いた問題

leetcode 217. Contains Duplicate
整数配列numsが与えられるので、重複の有無を判定してねって問題。

配列内に 同じ値が少なくとも2回以上出現する場合はTrueを返し、すべての要素が異なる場合はFalseを返す必要がある。

学び

• 重複判定はバリューを保持しないのであればsetが最有力
• アルゴリズムに触れる頻度が減ると過去取り組んだ解法を忘れてしまいがち。継続は力なり。
• 記事タイトルに使用技術書かないと振り返りがしづらい。

最初に考えた解法

重複を判定、ということでsetが使える気がしたが、ちょっと使い方を忘れてしまったのでdictでhashmapを作り、numsと長さの比較をすることで判定する方法を考えた。

first.py

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        map = {}

        for i, num in enumerate(nums):
            map[num] = i
        
        if len(map) == len(nums):
            return False
        else:
            return True

これで一発正解。よしよし。

時間計算量、空間計算量ともに$O(n)$だが、最適解はどうなのだろうか。

正解

べスプラは下記。

answer.py

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

みじか！！！
思わず叫びました。

回答の肝はやはりset。
dictと同じくハッシュ値を内部で使用しているため値の探索が$O(1)$と極めて速く、値の重複を許さないため重複判定に一番効果的。

今回の問題はインデックス等をバリューに持つ必要がないため、setを使うほうがコード量が少なくていいよねって結論になる。

ただこちらも時間・空間計算量ともに$O(n)$となる。
forがないのになぜ時間計算量まで？と思ったが、setを使っていると内部で下記のような処理が回るため、結局$O(n)$になるそう。

in_set.py

s = set()
for x in nums:      # ← ここが「見えない for」
    s.add(x)

return len(nums) != len(s)

それでも無駄なバリューを保持するdictよりもメモリ使用量は減りそうですし、実装時間もわかりやすさもべスプラのほうがいいですね。

最速別解

上記二つは引数すべてを確認する方法。
走査中に重複があったら返却するほうが理論上早くなります。それが下記。

fastest.py

seen = set()
for num in nums:
    if num in seen:
        return True
    seen.add(num)
return False

感想

setを使った重複判定、過去にやった気がするんだけどな...
「継続は力なり」は忘却曲線的にも正しそうなので頑張ります。

あと、タイトルに使った技術を書かないと過去記事検索がめんどくさいこともわかったので、今後気を付けるようにしようと思いました。