点名
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 44 ms, 内存: 15.8 MB
/*
* 思路：
* 使用IntStream和filter方法，找到第一个位置i，使得records[i] != i
* 这个位置i即为缺失的学号
*/
import java.util.stream.IntStream;
public class Solution {
public int findMissingNumber(int[] records) {
return IntStream.range(0, records.length)
.filter(i -> records[i] != i)
.findFirst()
.orElse(records.length);
}
}解释
方法:
题解采用了二分查找的方法来寻找缺失的学号。由于数组是升序的，如果没有缺失，每个元素的值应该等于其索引。算法利用这一点，对数组进行二分查找。当中间元素的值等于其索引时，意味着缺失的学号在右侧，因此调整左边界；如果不等，说明缺失的学号在左侧或就是当前的中间位置，因此调整右边界。最终，左边界 'lo' 将停在缺失学号的位置。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在nums[mid]等于mid时，可以确定缺失的学号在右侧？
▷🦆
在二分查找过程中，如果nums[mid]不等于mid，为何判定缺失的学号可能就是当前的mid位置？
▷🦆
算法在最后返回lo的值作为缺失学号的依据是什么？
▷🦆
如果数组中没有缺失的学号（即所有学号都齐全），这种算法是否会返回正确的结果？
▷