【アルゴリズム脳トレ】leetcode easy 268 missing number

こんにちは

今回の学びは

・完璧な情報があれば欠けている情報は見つかる

問題は。。。

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

スペース使えば、以下のようなhashを使うのを思いつきました。

class Solution_space:
    def missingNumber(self, nums: List[int]) -> int:
        memo = [0] * (len(nums)+1)
        for i, n in enumerate(nums):
            memo[n] = 1
        print(memo)
        for i, n in enumerate(memo):
            if memo[i] == 0:
                return i
        return None

どうやらスペースは使わないで欲しいとう制約があります。

更に、この問題は入力は常に0 ~ nとういう制約があるので

足し算してしまえば書けているピースがわかるよう算段です

ということで学びは

・完璧な情報があれば欠けている情報は見つかる

実装後です。timespace analysis (時間とスペースの分析）は　O(n)

spaceはO(1)です

まとめ

・完璧な情報があれば欠けている情報は見つかる

以上です