題目出處

268. Missing Number

難度

easy

個人範例程式碼

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        if not nums:
            return 0

        num_set = set(nums)
        n = len(nums) + 1
        for i in range(n):
            if i not in num_set: # O(1)
                return i

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

因為 list 搜尋是 O(N) 時間，
為了加速，先轉成 hashset，搜尋時間變成 O(1)

input handling

如果沒有 input，return 0

Boundary conditions

for loop 控制範圍

個人範例程式碼 – set

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        if not nums:
            return 0

        num_set = set([x for x in range(len(nums)+1)])
        return (num_set - set(nums)).pop()

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

set – set，找到缺少的內容

set.pop() 可以取得 set 裡面的內容，例如從 {2} 中取得 2

input handling

如果沒有 input，return 0

Boundary conditions

for loop 控制範圍

Reference

• 寻找缺失的数 · Missing Number