题目一

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：
输入：n = 1, bad = 1
输出：1

提示：
1 <= bad <= n <= 231 – 1

题解

这可以理解成一个二分查找求左边界的问题。

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        # 左边界
        left = 1
        right = n
        while left<=right:
            mid = (left+right)//2
            if isBadVersion(mid):
                right = mid-1
            if not isBadVersion(mid):
                left = mid+1
        return left

题目二

268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都独一无二

题解

此题解法有多种思路：

先排序，然后二分查找，当出现位置索引和数字不匹配时，该位置本该出现的数字就是缺少的那一个数字。
运用异或的性质，例如1 ^ 1 ^ 2 ^ 2 ^ 3 = 3 的性质，将完整数组内数字与该数组数字全部异或，得到的值就是缺的那一个数字。

复杂度分析
时间复杂度：O(n)，其中 n 是数组 nums 的长度。需要对 2n+1 个数字计算按位异或的结果。
空间复杂度：O(1)。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        xor = 0
        for i, num in enumerate(nums):
            # 1^1^2^2^3=3
            xor = xor ^ i ^ num
        return xor ^ len(nums)