题目

剑指 Offer 53 - II. 0～n-1中缺失的数字

思路1

• 排序数组找数字使用二分法
• 通过题目，我们可以得到一个规律：
  • 如果数组的索引值和该位置的值相等，说明还未缺失数字
  • 一旦不相等了，从左到右第一个不相等位置的索引值就是缺失的数字的值
  • 所以我们使用二分法查找第一个索引值和数组的值不相等的位置，此时索引值就是我们要的结果了
• 如果没有缺失，就输出数组的长度

代码

class Solution {
    public int missingNumber(int[] nums) {
        int length = nums.length;
        int start = 0;
        int end = length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            // 索引值和该位置的值不相等，说明有可能该位置的索引值就是缺失的数字的值
            if (nums[mid] != mid) {
                // 如果该位置是缺失的位置，那么mid要么为第一个元素，要么前一个元素的值和索引值相等
                if (mid == 0 || nums[mid-1] == mid-1) {
                    // 找到
                    return mid;
                } else {
                    // 如果不是缺失的值，那么说明还在左边，于是继续二分查找左边
                    end = mid - 1;
                }
            } else {
                // 相等的情况下，我们二分查找右边的
                start = mid + 1;
            }
        }

        // 如果找了一圈，都没有缺失，那么start就会等于length，此时返回length的值就好
        if (start == length) {
            return length;
        }

        return -1;
    }
}

复杂度分析

• 时间复杂度：\(O(logN)\)
• 空间复杂度：\(O(1)\)