Offer准备指南 - 题目53：找出0到n-1之间遗漏的数（巧用二分法和位操作）
最编程
2024-07-20 15:32:36
...
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 <= 数组长度 <= 100002. 解题
2.1 充分利用题目信息
nums[i] != i，就是缺少的数 i ，都不少的话，少的就是n = nums.size()class Solution {
public:
int missingNumber(vector<int>& nums) {
for(int i = 0; i < nums.size(); ++i)
if(nums[i] != i)
return i;
return nums.size();//有个例子是 [0],答案预期 1
}
};2.2 位运算
class Solution {
public:
int missingNumber(vector<int>& nums) {
int i, ans = nums.size();
for(i = 0; i < nums.size(); ++i)
ans = ans^i^nums[i];
return ans;
}
};2.3 二分查找
class Solution {
public:
int missingNumber(vector<int>& nums) {
int l = 0, r = nums.size()-1, mid;
while(l < r)//有等于号，则不能退出循环
{
mid = l+((r-l)>>1);
if(nums[mid] == mid)//左边都不缺
l = mid+1;
else//不相等，左边肯定缺了东西，可能在当前位置
r = mid;
}
if(nums[l] == l)//全部有序，前面全部不缺
return l+1;
return l;//这里写 r 也可以
}
};