2021-02-21 剑指 Offer 53 - II. 0～n

题目地址

https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

题目描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
 
限制：
1 <= 数组长度 <= 10000

思路

1. n-1个数有序并且只少一个数，我们只需要遍历数组，如果数组元素不等于下标，说明缺失的就是这个元素, 遍历完了还没找到说明缺失的是最后一个元素。
2. 既然有序，可以用二分法进一步优化，找到第一个下标不等于元素值的，找不到就说明缺失的是最后一个元素。
3. 如果缺失的是最后一个元素，其实可以立马判读出来（最后一个元素值等于下标，直接返回n-1）。
   PS: 其实因为缺失的位置是随机的

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/21 11:46 下午
 */
public class MissingNumber {
    public static void main(String[] args) {
        int[] nums = {0,1};
        int result = missingNumber(nums);
        System.out.println(result);
        result = missingNumberV2(nums);
        System.out.println(result);
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.9 MB, 在所有 Java 提交中击败了55.59%的用户
     */
    private static int missingNumberV2(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        if (nums[right] == right) {
            return right + 1;
        }
        while (left < right) {
            int half = left + (right - left) / 2;
            if (nums[half] != half) {
                right = half;
            } else {
                left = half + 1;
            }
        }
        return left;
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.8 MB, 在所有 Java 提交中击败了71.60%的用户
     */
    private static int missingNumber(int[] nums) {
        int right = nums.length - 1;
        if (nums[right] == right) {
            return right + 1;
        }
        for (int i=0; i<nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return -1;
    }
}