题目
0R(682}HT9~04}C7H57YA.png
思路
遍历数组，找到序号与值不同的一项，时间复杂度o(n)，空间复杂度o(1)
优化
用二分法遍历数组，时间复杂度o(log2)，空间复杂度o(1)
1. 初始化
上边界为0，下边界为len(nums)-1.
2. 循环二分
- 计算中点 m = (i + j) // 2 ，其中 "//" 为向下取整除法；
- 若nums[m] = m，则 “右子数组的首位元素” 一定在闭区间 [m + 1, j]中，因此执行 i = m + 1；
- 若nums[m] !=m ，则 “左子数组的末位元素” 一定在闭区间 [i, m - 1]中，因此执行 j = m - 1；
3. 返回值
跳出时，变量 i 和 j 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 i 即可
代码
class Solution {
public int missingNumber(int[] nums) {
int end = nums.length-1,start = 0;
int middle = 0;
while(end>=start){
middle = (end+start)/2;
if(nums[middle]>middle){
end = middle-1;
}else{
start = middle+1;
}
}
return start;
}
}
疑问
为什么遍历占用的内存比二分法低？
1`(DL%K@`JIX1M(3XC`M2ZB.png
