题目一
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)
题目来自LeetCode。
