题目：
题解：
1、普通遍历：
思路一：正常是后一个比前一个大一，找不正常的
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// 遍历求解，思路是正常是后一个比前一个大一，找不正常的
class Solution {
public int missingNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (i == nums.length -1){
if (nums[0] != 0) {
return 0;
}else return nums[i] + 1;
}
if (i != nums.length-1){
if (nums[i+1] == nums[i] + 1) {
continue;
}else {
return nums[i] + 1;
}
}
}
// 如果为空返回0
return 0;
}
}
思路二：正常是数组下标位置对应数组的值，找不正常的
代码：
1
2
3
4
5
6
7
8
9class Solution2 {
public int missingNumber(int[] nums) {
for (int i = 0;i<nums.length;i++){
if (nums[i]!=i) return i;
}
// 如果是前面是连续的，后面没有东西，则得返回长度;
return nums.length;
}
}
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
2、二分法实现
思路：划分为俩个组，一个是正常的组，一个比自身位置大于1的组，最后left>right,输出。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14// 二分法实现，思路就是划分为俩个组，一个是正常的组，一个比自身位置大于1的组，最后left>right,输出
class Solution3 {
public int missingNumber(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > mid) {
right = mid -1;
}else left = mid + 1;
}
return left;
}
}
复杂度分析：
- 时间复杂度：O(logn)
- 空间复杂度：O(1)