いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】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)です

 

まとめ

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

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.