本文共 822 字，大约阅读时间需要 2 分钟。

为了找出缺失的数字，我们可以使用二分查找算法，因为数组是有序的。以下是详细的解决方案：

方法一（二分查找）

解题思路

我们需要找到一个在0到n-1范围内的数字，这个数字不在给定的递增排序数组中。数组的长度为n-1，意味着缺失的数字在0到n-1之间。我们可以利用二分查找来高效地缩小查找范围。

代码实现

public class Solution {    public int missingNumber(int[] nums) {        int low = 0;        int high = nums.length - 1;        while (low <= high) {            int mid = low + (high - low) / 2;            if (nums[mid] > mid) {                high = mid - 1;            } else if (nums[mid] < mid) {                low = mid + 1;            } else {                low = mid + 1;            }        }        return low;    }}

复杂度分析

• 时间复杂度：O(logn)，因为二分查找的时间复杂度是logn。
• 空间复杂度：O(1)，由于只使用了常数额外空间。

结论

使用二分查找法，我们可以在O(logn)时间复杂度内找到缺失的数字，这是一个高效且优雅的解决方案。

转载地址：http://bsjtz.baihongyu.com/