53_2_0~n-1中缺失的数字.md

0~n-1中缺失的数字

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

分析

1. 直接遍历

寻找不在对应位置上的数：nums[i] != i ，如果找到了，返回 i ；否则， 返回 n 。

时间复杂度为 O(logn) 。

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }
}

2. 求和法

求长度为 n 的数组的和为 sum = n * (n + 1) / 2 。

我们求得和之后，再减去 nums 数组中的元素， sum 中剩下的元素就是缺失的元素。

时间复杂度为 O(n) 。

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = n * (n + 1) / 2;
        for (int num: nums) sum -= num;
        return sum;
    }
}

3. 计数排序

我们使用一个长度为 n + 1 的数组来储存元素的值。遍历 nums 数组，将每个 cnt[num] ++ 。之后再遍历 cnt 数组，如果对应的 cnt[i] = 0 ，说明是缺失的元素。

时间复杂度为 O(n)。

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int[] cnt = new int[n + 1];
        for (int num: nums) cnt[num]++;
        for (int i = 0; i <= n; i++) {
            if (cnt[i] == 0) return i;
        }
        return -1;
    }
}

4. 二分法

对于排序数组的搜索问题，直接考虑二分查找法。

通过观察可以发现，数组是排序的，那么在缺失数字的左边，一定有 nums[i] = i ，在缺失数字的右边，每个数字都前移的一位，所以一定有 nums[i] != i 。通过此规律可以进行二分。

时间复杂度为 O(logn) 。

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