文章目录
- 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;}
};