0～n-1中缺失的数字

Leetcode Link: 剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（LeetCode）

题目

解法一

思路： 红蓝二分法。

注意r的初始化以及返回的是什么，什么是isBlue()

题解：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        l = -1
        r = len(nums)
        while(l+1 != r):
            mid = (l + r) >> 1
            if nums[mid] == mid:  # isBlue()
                l = mid
            else:
                r = mid
        return r

解法二

思路： sum([1:n]) - sum(nums)即为结果。

题解：

class Solution: 
	def missingNumber(self, nums: List[int]) -> int: 
		return sum([i for i in range(len(nums)+1)]) - sum(nums)

解法三

思路： 哈希 Counter 之后遍历即可。

不过不好

题解：

启发和联系