一个长度为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
我们可以使用二分查找的方式来做这一题,我们知道每个索引对应相应的值,我们从题目看到,索引正常情况是等于值的,而且索引和值的关系只有
索引==索引对应值
,索引对应值-1==索引
,使用二分找到索引对应值-1==索引
这一块然后找到缺失的数字,注意一点很容易误解的地方,比如给的数组是[0]
,那么缺失的数字是1,给的数组是[0,1,2]
,那么缺失的数字是3,因为他给的数组有一个缺失的数字。所以二分在这种情况就不奏效了,因为不存在索引对应值-1==索引
,所以我们还要在数组添加一个元素(这个元素是nums.size()),当上述情况出现后,最后返回的就是nums.size这个我们需要的数字
class Solution {
public:
int missingNumber(vector<int>& nums) {
int l=0;
nums.push_back(nums.size());
int r=nums.size()-1;
int mid;
while(l<r)
{
mid=l+(r-l)/2;
if(nums[mid]>mid)
r=mid;
else if(nums[mid]==mid)
l=mid+1;
}
return l;
}
};
class Solution {
public int missingNumber(int[] nums) {
int arr[]=new int[nums.length+1];
for(int i=0;i<arr.length-1;i++)
{
arr[i]=nums[i];
}
arr[arr.length-1]=arr.length-1;
int l=0;
int r=arr.length-1;
int mid;
while(l<r)
{
mid=l+(r-l)/2;
if(arr[mid]>mid)
r=mid;
else if(arr[mid]==mid)
l=mid+1;
}
return l;
}
};
本文地址:https://blog.csdn.net/qq_45737068/article/details/107487226
如对本文有疑问, 点击进行留言回复!!
Android 4.0使用Kotlin调用C语言以及汇编语言
Java Class.forName()用法和newInstance()方法原理解析
网友评论