剑指offer【53】：0~n-1数组缺失值

题目：

思路+代码：

法一：暴力法，首尾指针
思路：初始化首尾指针，i=0,j=len(nums); 每次移动一个数，判断nums[i] ?= i or nums[j-1] ?= j
时间复杂度：O(n)
空间复杂度：O(1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 思路：初始化首尾指针，i=0,j=len(nums); 每次移动一个数，判断nums[i] ?= i  or nums[j-1] ?= j
        # 时间复杂度：O(n)
        # 空间复杂度：O(1)
        if not nums: return 
        i, j = 0, len(nums)
        while i <= j:
            
            if nums[i] != i:
                return i
            if nums[j-1] != j:
                return j
            i += 1
            j -= 1

法二：二分查找
思路：利用二分查找
if nums[mid] != mid, 则那个数在mid左边；否则在右边；
每次i 在新子数组的开始，j在新子数组的末尾；
时间复杂度：O(log(n))
空间复杂度：O(1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 思路：利用二分查找
        #   if nums[mid] != mid, 则那个数在mid左边；否则在右边；
        #   每次i 在新子数组的开始，j在新子数组的末尾；
        #   时间复杂度：O(log(n))
        #   空间复杂度：O(1)
        if not nums: return 
        i, j = 0, len(nums)-1
        while i <= j:
            temp = (i + j) // 2
            if nums[temp] == temp:
                i = temp + 1
            else:
                j = temp -1
        return i