面试题53

方法一：二分查找。

class Solution(object):
    # 二分法
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i, j = 0, len(nums) - 1
        while i <= j:
            # 向下取整
            mid = (i + j) // 2
            if nums[mid] == mid:
                i = mid + 1
            else:
                j = mid - 1
        return i

方法二：暴力解。

class Solution(object):
    # 暴力
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n != nums[-1]:
            return n
        for i in range(len(nums)):
            if nums[i] != i:
                return i