如何查找递增连续数组中缺失的数字

在一个长度为n的递增数组中,数组中元素范围是0 ~ n-1,如何在这个递增连续数组中查找缺失的数字?

分析下:

1. 排序数组中的搜索算法,首先想到的就是二分法查找

2. 丢失的数字之前的左子数组:nums[m] = m, 需要找到第一个nums[m] > m的数组索引值即可.

例如数组nums={0, 1, 2, 3, 4, 6, 7 }, 在索引m<5时,nums[m] = m;在m>=5时,nums[m]>m;

一起看下遍历过程

1. 确定边界指针:左指针l = 0; 右指针r= length -1;

中间值指针m = (l + r) /2 = 3;

2. 移动边界指针

Nums[3] = 3,左指针右移,同时,已经知道了m指针位置,指针值与元素值是相同的,查找值一定是在[m+1,r]区间中,所以左指针移动到m+1位置.

继续计算m指针值 m = (4 + 6) /2 =5;

3. num[5] < 6, 右指针左移,我们并不能确定m指针的前一位的元素值和索引值是否相同,但采用贪心策略,认为也是不同的,所以右指针移动位置为r = m-1;

这里多解释下,即使m-1这个位置是相同的, 也会被后续的左指针r=m+1的情况下处理掉,此处不好理解,需多多体会.

继续计算m指针值,m= (l + r)/2=(5 + 5)/2=5;

这时发现左,中,右三指针都指向了num[4], 但4并不是我们想要的值.

在处理边界值的时候,在(i == r)的时候,还多需要多遍历一次,向右移动左指针一次.

4. 这时,左指针值便是最后想要的值.

所以我们的遍历条件为(l<=r),最后左指针位置即为缺失的结果值.

此处较难理解,需好好体会.

综上,对于有序数组的查找,一般都会使用二分法查找.在查找数据的时候,注意左右边界指针的移动.以及遍历标记(l<=j)即可.

附上代码:

https://github.com/coderworld968/algorithm/blob/master/src/main/java/arithmetic/MissingNumber.java