LeetCode 每日一题 [67] 0～n-1中缺失的数字

LeetCode 0～n-1中缺失的数字 [简单]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof

示例 1:

输入: [0,1,3]
输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：

1 <= 数组长度 <= 10000

题目分析

解法1

因为长度为 n - 1,每个数据都是唯一的，而且每个数字都是在 0 - n -1 之间 而且只有一个不在此范围中 可以迭代，根据数组下标的特性 只要 nums[i] != i;则返回i 只能从小向大迭代

解法2

顺序数组查找问题 解决思路就是二分法

代码实现

public class MissingNumber {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(missingNumber(nums));
    }

    public static int missingNumber1(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    public static int missingNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0] == 0 ? 1 : 0;
        }
        int i;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        if (i == nums.length) {
            return i;
        }
        return -1;
    }
}