0~n-1中缺失的数字
约 752 字大约 3 分钟
题目：
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
分析：
方法一：
先用公式 n(n-1)/2 求出数字 0~n-1 的所有数字之和，记为s1。接着求出数组中所有数字的和，记为s2。那个不在数组中的数字就是 s1-s2。这种解法需要 O(n) 的时间求解数组中所有数字的和。显然，该解法没有有效利用数组是递增排序的这一特点。
方法二：
0~n-1 中数字是排序的，因此数组中一开始的一些数字与它们的下标相同。如果不在数组中的数字记为 m，那么所有比 m 小的数字下标都与它们的值相同。那么，数组中 m+1 处在下标 m 的位置，m+2 处在下标为 m+1 的位置。
基于二分查找：如果中间元素的值和下标相等，那么下一轮查找只需要查找右半边；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标相等，这意味着这个中间的数字正好是第一个值和下标不相等的元素，它的下标就是在数组中不存在的数字；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标不相等，这意味着下一轮查找我们只需要在左半边查找即可。
代码：
基于方法二
class MissingNumberSolution {
private static int getMissingNumber(int[] data, int length) {
if (null == data || length <= 0) {
return -1;
}
int left = 0;
int right = length - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (data[mid] != mid) {
if (mid == 0 || data[mid - 1] == mid - 1) {
return mid;
}else{
right = mid - 1;
}
}else{
left = mid + 1;
}
}
if (left == length) {
return length;
}
return -1;
}
public static void main(String[] args) {
int[] data = {0, 1, 2, 3, 4, 5, 7, 8};
System.out.println(getMissingNumber(data, 9));
}
}
牛客解法
class NowCoderMissing {
// 从 0 ~ n如果没有缺失，那个肯定是奇偶交替。缺失了数那么肯定会出现奇数奇数或者偶数偶数的情况
// 例子： 0 1 2 3 4 5 7, 缺失了6（判断给出的二进制是奇数或偶数只要看最后一位就可以了，即numbers[i][0]
// 从0~n遍历， 0 % 2 是否等于 numbers[0][0] ----- 5 % 2 是否等于 numbers[5][0], 6 % 2是否等于numbers[6][0] 发现是缺失了6
private static int findMissing(int[] data, int length) {
for (int i = 0; i < length; i++) {
if (i % 2 != data[i] % 2) {
return i;
}
}
return length;
}
public static void main(String[] args) {
int[] data = {0, 1, 2, 3, 4, 5, 7, 8};
System.out.println(findMissing(data, 9));
}
}