今日份题目:
一个长度为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();}
};
提交结果
暴力查找
二分查找
欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!