leetcode-剑指offer 53

点击:题目链接:一个长度为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. 该数组是递增有序的
  2. 数字只出现一次
  3. 只有一个数不再数组内

因此首先我们想到的就是暴力的方法,逐一扫描找出该数

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int missingNumber(vector<int>& nums) {
int tmp = 0;
for(int i=0; i<nums.size(); i++){
if(tmp != nums[i]) break; //如果发现不同的就中断当前for循环
tmp++;
}
return tmp; //返回最终值
}
};

思路二

根据暴力的解法,我们发现当低位出现数组下标和元素的值不匹配的时候,那么之后的所有的数都是不匹配的。因此我们可以使用二分法(双指针)。首先查看中值是否符合条件,若不相等右指针缩小范围。若相等,将左指针移动到中值,下一部分的二分之一。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int missingNumber(vector<int>& nums) {
int l=0, r=nums.size()-1;
int mid;
while(l <= r){
mid = (l+r)/2;
if(nums[mid] != mid) r= mid-1; //不等,右指针前挪,左指针不动
else l = mid+1; //相等,左指针右挪,右指针不动
}
return l;
}
};
作者

Dylan Zhu

发布于

2021-03-15

更新于

2021-03-23

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...