在一个长度为n的递增数组中,数组中元素范围是0 ~ n-1,如何在这个递增连续数组中查找缺失的数字?
分析下:
1. 排序数组中的搜索算法,首先想到的就是二分法查找
2....丢失的数字之前的左子数组:nums[m] = m, 需要找到第一个nums[m] > m的数组索引值即可....移动边界指针
Nums[3] = 3,左指针右移,同时,已经知道了m指针位置,指针值与元素值是相同的,查找值一定是在[m+1,r]区间中,所以左指针移动到m+1位置....继续计算m指针值,m= (l + r)/2=(5 + 5)/2=5;
这时发现左,中,右三指针都指向了num[4], 但4并不是我们想要的值....在处理边界值的时候,在(i == r)的时候,还多需要多遍历一次,向右移动左指针一次.
4. 这时,左指针值便是最后想要的值.
所以我们的遍历条件为(l<=r),最后左指针位置即为缺失的结果值.
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
