题目地址
https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
题目描述
一个长度为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
思路
- n-1个数有序并且只少一个数，我们只需要遍历数组，如果数组元素不等于下标，说明缺失的就是这个元素, 遍历完了还没找到说明缺失的是最后一个元素。
- 既然有序，可以用二分法进一步优化，找到第一个下标不等于元素值的，找不到就说明缺失的是最后一个元素。
- 如果缺失的是最后一个元素，其实可以立马判读出来（最后一个元素值等于下标，直接返回n-1）。
PS: 其实因为缺失的位置是随机的
题解
/**
* @Author: vividzcs
* @Date: 2021/2/21 11:46 下午
*/
public class MissingNumber {
public static void main(String[] args) {
int[] nums = {0,1};
int result = missingNumber(nums);
System.out.println(result);
result = missingNumberV2(nums);
System.out.println(result);
}
/**
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
* 内存消耗：38.9 MB, 在所有 Java 提交中击败了55.59%的用户
*/
private static int missingNumberV2(int[] nums) {
int left = 0;
int right = nums.length - 1;
if (nums[right] == right) {
return right + 1;
}
while (left < right) {
int half = left + (right - left) / 2;
if (nums[half] != half) {
right = half;
} else {
left = half + 1;
}
}
return left;
}
/**
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
* 内存消耗：38.8 MB, 在所有 Java 提交中击败了71.60%的用户
*/
private static int missingNumber(int[] nums) {
int right = nums.length - 1;
if (nums[right] == right) {
return right + 1;
}
for (int i=0; i<nums.length; i++) {
if (nums[i] != i) {
return i;
}
}
return -1;
}
}
