LeetCode.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 中。

示例 5:

输入： nums = [0]
输出： ["0"]

提示:

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

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

思路分析

排序

这个思路很简单，当我们排序之后，如果没有数字丢失的话，那么下标和该下标对应的值应该是一致的，所以我们只要遍历一遍之后，发现不相等的话即是答案。

AC代码

class Solution {
    fun missingNumber(nums: IntArray): Int {
        nums.sort()
        nums.forEachIndexed { index, value ->
            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 = 0
        nums.forEach {
            sum += it
        }
       return ((0 + nums.size) * (nums.size + 1) / 2) - sum
    }
}

位运算

我们知道异或的性质：x ^ x = 0，x ^ 0 = x。

而给定的数组中只缺失了一个数，所以，我们可以把 0 到 n 中所有的数都补充上，那么，只有一个数出现了一次，我们把所有这些数进行异或最后的结果就是那个要寻找的数。

AC代码

class Solution {
    fun missingNumber(nums: IntArray): Int {
         var result = 0
        for(index in 0 until nums.size){
            result =result.xor(nums[index]).xor(index)
        }
        return result.xor(nums.size)
    }
}

总结

此题我觉得关键的就是找到异或的解法吧，不过不做多了很难条件反射的想到这种解法，一般还是生活中的思想去考虑问题，所以，多多刷题吧。

参考

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

【宫水三叶】一题五解 :「排序」&「计数」&「原地哈希」&「数学」&「异或」 - 丢失的数字 - 力扣（LeetCode） (leetcode-cn.com)

【彤哥来刷题啦】一题两解：求和 & 异或 & 周末了简单点！ - 丢失的数字 - 力扣（LeetCode） (leetcode-cn.com)