python--剑指offer--53 - II. 0～n-1中缺失的数字

from typing import List


class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 注意题目要求数组长度为n-1,则该数组的取值范围为[0, n-1]共n个数,数组中保存这n个数的(n-1)个数,需找出未保存的那个数
        l, r = 0, len(nums) - 1
        if r == nums[r]:  # 当未保存的那个数为最后那个数(n-1)时
            return r + 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == mid:
                l = mid + 1
            elif nums[mid-1] == mid - 1:
                break
            else:
                r = mid - 1
        return mid


if __name__ == '__main__':
    solution = Solution()
    nums = [0, 1, 2, 3, 4, 5, 6, 7, 9]
    # nums = [0, 1, 3]
    # nums = [0]
    res = solution.missingNumber(nums)
    print(res)

[题目源于leetcode]