LeetCode.268 丢失的数字

题目描述：

268. 丢失的数字 - 力扣（LeetCode） (leetcode-cn.com)

给定一个包含 [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 中的所有数字都 独一无二

思路分析

排序

由题意可知，当一个数组是有序的时候，相邻两数一定是相差1的，所以我们将数组排序后很容易就知道缺失的是哪个数字了。

这里要注意处理边界情况，缺失的数字是首位，这个可以放在for循环里处理掉，如果丢失的是末位，则可以在循环外处理，也就是最后的兜底返回其实就是for循环当中没有产生返回。

AC代码

class Solution {
    fun missingNumber(nums: IntArray): Int {
        nums.sort()
        for ((index, value) in nums.withIndex()) {
            if (index != value) return index
        }
        return nums.size
    }
}

数学法

我们可以用 高斯求和公式 求出 [0..n] 的和，减去数组中所有数的和，就得到了缺失的数字。高斯求和公式即

∑i=0ni=n(n+1)2\sum_{i=0}^{n}i = \frac{n(n+1)}{2}∑i=0n​i=2n(n+1)​

AC代码

class Solution {
    fun missingNumber(nums: IntArray): Int {
        var sum = (1 + nums.size) * nums.size / 2
        for(i in nums){
            sum -= i
        }
        return sum
    }
}

总结

这题还算简单，但是数学法其实有溢出风险的，可能test case里没有这个情况，所以通过了

参考

缺失数字 - 丢失的数字 - 力扣（LeetCode） (leetcode-cn.com)