文章目录
- 1.题目
- 2.思路
- 3.代码
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
2.思路
最简单的方式遍历，用二分的方法,数组中的每个元素的值都应该等于它的索引（nums[i] == i）。当某个位置的值和它的索引不相等时，说明缺失的数字在该位置或之前
3.代码
class Solution {
public:int missingNumber(vector<int>& nums) {int left = 0;int right = nums.size() - 1;// 如果数组中最大元素等于它的索引值，说明缺失的数字是 n// 比如 [0,1,2,3] 缺 4，那么 nums[3] == 3，此时返回 4if (nums[right] == right) return right + 1; // 二分查找的过程中，如果发现某个位置的值和索引不匹配，说明缺失的数字在该位置或之前// [0, 1, 3] 缺 2 的情况就是这种情况while (left < right) {int mid = left + (right - left)/2; // 取中间位置// 如果 nums[mid] == mid 说明前半部分没有缺失数字，继续查找右半部分if (nums[mid] == mid) {left = mid + 1;} else {// 否则，缺失的数字在左半部分或当前 mid 位置right = mid;}}// 最终 left 的位置就是缺失的数字return left;}
};