每天一道leetcode：剑指 Offer 53 - II. 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

题目思路及代码

方法一：暴力查找

从头到尾，用一个int型数据记录数组当前位置本应为那个数，然后两者进行判断，如果不同就返回记录的数，相同就到下一个继续判断。

class Solution 
{
public:int missingNumber(vector<int>& nums) {int c=0;for(int i=0;i<nums.size();i++) {if(nums[i]!=c) return c;c++;}return nums.size();}
};

方法二：二分查找

循环遍历本应出现的所有的数，判断是否存在于数组中，如果不存在就返回这个数，如果所有数都存在，说明确实的是数组长度的那个数。二分查找可以使时耗降低。

class Solution 
{
public:bool find(vector<int>& nums,int target)//二分查找target是否在数组中{int l=0,r=nums.size()-1,n=nums.size();int mid;while(l<=r){mid=(l+r)/2;if(nums[mid]>target){r=mid-1;}else if(nums[mid]<target){l=mid+1;}else return true;}return false;}int missingNumber(vector<int>& nums) {for(int i=0;i<nums.size();i++) //遍历所有应该出现的数判断是否存在{bool cur=find(nums,i);if(cur==false) return i;}return nums.size();}
};

提交结果

暴力查找

二分查找

  欢迎大家在评论区讨论，如有不懂的代码部分，欢迎在评论区留言！