title: 每日一练（25）：0～n- 1 中缺失的数字
categories:[剑指 offer]
tags:[每日一练]
date: 2022/02/24
每日一练（25）：0～n- 1 中缺失的数字
一个长度为 n - 1 的递增排序数组中的所有数字都是惟一的，并且每个数字都在范畴 0～n- 1 之内。在范畴 0～n- 1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输出: [0,1,3]
输入: 2
示例 2:
输出: [0,1,2,3,4,5,6,7,9]
输入: 8
限度：
1 <= 数组长度 <= 10000
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
办法一：二分查找
二分求边界，其实就是求数组中等于 target 的元素的范畴边界，如果数组中不存在等于 target 的元素，那求得的左右边界的值就是一样的。
int missingNumber(vector<int>& nums) {
int l = 0;
int r = nums.size();
int m = 0;
while (l < r) { // 二分查找
m = (l + r) / 2;
if (nums[m] == m) {l = m + 1;} else {r = m; // 失去缺失的那个数}
}
return r;
}办法二：数学法（等差数列）
数组有 n 个数，但 0 到 n 有 n + 1 个数，依据等差数列求和可得 sum = (0+n)*(n+1)/2
而后总和减去数组所有数，就是缺失的那个数
int missingNumber(vector<int>& nums) {int n = nums.size();
int sum = (0 + n)*(n + 1) / 2; // 等差数列求和
for (int i : nums) {sum -= i; // 总和减去数组所有数，就是缺失的那个数}
return sum;
}