【Leetcode算法题】268. 丢失的数字

By Long Luo

今天Leetcode的每日一题是：268. 丢失的数字，题目如下：

268. 丢失的数字

给定一个包含[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数。

示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围[0,3]内。2是丢失的数字，因为它没有出现在 nums 中。

示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有2个数字，所以所有的数字都在范围[0,2]内。2是丢失的数字，因为它没有出现在nums中。

示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有9个数字，所以所有的数字都在范围[0,9] 内。8是丢失的数字，因为它没有出现在nums中。

示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围[0,1]内。1是丢失的数字，因为它没有出现在 nums 中。

提示：
n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

方法一： 暴力 + 排序

思路与算法：

这是一道简单题。很简单，首先想到的方法是先进行排序，然后遍历数组，找到值不同的那个数字，如果都相同，那么结果就是$len$。

代码如下所示：

public int missingNumber(int[] nums) {
    int len = nums.length;
    Arrays.sort(nums);
    for (int i = 0; i < len; i++) {
        if (i != nums[i]) {
            return i;
        }
    }

    return len;
}

复杂度分析：

• 时间复杂度：$O(n \log n)$，其中$n$是数组$\textit{nums}$的长度。排序的时间复杂度是$O(n \log n)$，遍历数组寻找丢失的数字的时间复杂度是$O(n)$，因此总时间复杂度是$O(n \log n)$。

• 空间复杂度：$O(\log n)$，其中$n$是数组$\textit{nums}$的长度。空间复杂度主要取决于排序的递归调用栈空间。

方法二： 数学

思路与算法：

从$0$到$n$的全部整数之和记为$\textit{total}$，根据等差数列求和公式，有：

$\textit{total} = \sum_{i=1}^n = \dfrac{n(n+1)}{2}$

将数组$\textit{nums}$的元素之和记为$\textit{arrSum}$，则$\textit{arrSum}$比$\textit{total}$少了丢失的一个数字，因此丢失的数字即为$\textit{total}$与$\textit{arrSum}$之差。

代码如下所示：

public String getHint(String secret, String guess) {
    int len = secret.length();
    int bulls = 0;
    int cows = 0;
    int[] secNums = new int[10];
    int[] gusNums = new int[10];
    for (int i = 0; i < len; i++) {
        int secVal = secret.charAt(i) - '0';
        int guessVal = guess.charAt(i) - '0';
        secNums[secVal]++;
        gusNums[guessVal]++;
        if (secVal == guessVal) {
            bulls++;
            secNums[secVal]--;
            gusNums[guessVal]--;
        }
    }

    for (int i = 0; i <= 9; i++) {
        cows += Math.min(secNums[i], gusNums[i]);
    }

    return bulls + "A" + cows + "B";
}

复杂度分析：

• 时间复杂度：$O(n)$，其中$n$是数组$\textit{nums}$的长度。需要$O(1)$的时间计算从$0$到$n$的全部整数之和以及需要$O(n)$的时间计算数组$\textit{nums}$的元素之和。

• 空间复杂度：$O(1)$。