【アルゴリズム】Missing Number で学ぶ『理想の総和 − 今の和』という発想

目次

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

解いた問題

leetcode 268 Missing Number
範囲[0, n]に含まれるn個の異なる数からなる配列numsが与えられるから、この範囲の中で配列に含まれていない唯一の数を返してねって問題。

学び

• 理想の総和 - 今の和 = 差分 という考え方がある
• それを計算するには数列のような考え方が必要
• /はfloatが返るので、整数を返したいなら偶数を割るときでも//2を使う

最初に考えた解法

ハッシュマップ使って出たかどうかをカウント、バリューが１つだけ異なるものが生まれるからそれを返却する、とかを考えた。
これを実行すると結局forで回して中身を確認する方式になる気がして計算量が多そう。

とはいえ他をぱっと思いつかなかったため実装。

...と思ったのだが、ハッシュマップ使わずにソートしたうえでnumsの長さを使ってfor回していけばどの値が抜けてるのかわかるのでは？ということに途中で気づいた。

それが下記。

first.py

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(0, len(nums)):
            if nums[i] != i:
                return i
        return len(nums)

これで正解。

時間計算量が$O(n)$で空間計算量が$O(1)$かな、と思い確認したら時間計算量が$O(Nlogn)$だった。

これはsortが$O(Nlogn)$であり、$O(n)$よりも大きいオーダーなのでそうなっている。
ソートはこれ以上早くならないのでボトルネックが移ってしまっていたようだ。

絶対最適解じゃない自信がある。

正解

正解は下記。総和を使うそう。

answer.py

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        return n * (n + 1) // 2 - sum(nums)

考え方は「0からnまでの総和 - numsの総和」を計算することによって、numsに存在しない数が浮き出るというもの。

0からnまでの総和は数列みたいなもので、「1 + 2 + ... + n-1 + n」と足す列と、「n + n-1 + ... + 1」のように逆から足す列と考えて、上下足すと「n+1 + n+1 + ... + n+1」のように、
n+1がn個生まれるから、元の総和はそれの半分ということ。

だから//2をしているのは整数を返したいから。
偶数*奇数をしているので/2で割ってもあまりは絶対出ないので答えとしては間違いではないものの、Pythonの仕様上整数同士の割り算でもfloatで帰ってしまう。

感想

スマートだ...

理想の総和 - 今の和 = 差分　という考え方は他アルゴリズムでも使うそう。
覚えておきます。