网页界面设计宽度和安全区,wordpress做seo,济南手机网站建设公司哪家好,网站制作与网页设计课程设计今日份题目#xff1a;
一个长度为n-1的递增排序数组中的所有数字都是唯一的#xff0c;并且每个数字都在范围0#xff5e;n-1之内。在范围0#xff5e;n-1内的n个数字中有且只有一个数字不在该数组中#xff0c;请找出这个数字。
示例1
输入: [0,1,3]
输出: 2
示例2 …今日份题目
一个长度为n-1的递增排序数组中的所有数字都是唯一的并且每个数字都在范围0n-1之内。在范围0n-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(vectorint nums) {int c0;for(int i0;inums.size();i) {if(nums[i]!c) return c;c;}return nums.size();}
};
方法二二分查找
循环遍历本应出现的所有的数判断是否存在于数组中如果不存在就返回这个数如果所有数都存在说明确实的是数组长度的那个数。二分查找可以使时耗降低。
class Solution
{
public:bool find(vectorint nums,int target)//二分查找target是否在数组中{int l0,rnums.size()-1,nnums.size();int mid;while(lr){mid(lr)/2;if(nums[mid]target){rmid-1;}else if(nums[mid]target){lmid1;}else return true;}return false;}int missingNumber(vectorint nums) {for(int i0;inums.size();i) //遍历所有应该出现的数判断是否存在{bool curfind(nums,i);if(curfalse) return i;}return nums.size();}
};
提交结果
暴力查找 二分查找 欢迎大家在评论区讨论如有不懂的代码部分欢迎在评论区留言
