268 丢失的数字

题目信息

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

题目地址：https://leetcode.cn/problems/missing-number/

示例 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 <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

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

题解一

也就是有从0到n共n+1个数字: 0 1 2 ... n

给出的数组是它们之间的n个数，缺少一个要找出来。（n个数是无序的）

如果是有序的那么哪个位置的数比前一个位置的数大2，那么说明缺少了一个数字，且数字的值和位置标相等。

如果排序去做很显然多此一举，我们要的只是那个数字，排序的消耗更大走了弯路。这组数字本身是一组连续的数字只是无序的摆放了且缺少一个。

因此我们可以准备一个原来的卡槽（n + 1个位置），将他们一一放进去，最后哪个位置留空那么就缺这个数字

实现当中容器用什么都可以我采用的数组，创建一个n+1的卡槽，初始化里面都是0，因此只需要把有值的改为1，完成后剩下只有一个位置为0，这个位置即是缺失的数字。

public int missingNumber(int[] nums) {
    byte[] arr = new byte[nums.length + 1];
    for(int i = 0; i < nums.length; i++){
        int num = nums[i];
        arr[num] = 1;
    }
    for(int i = 0; i < arr.length; i++){
        if(arr[i] == 0){
            return i;
        }
    }
    return -1;
}

因为我们的数组只存0/1，节约空间所以使用byte类型（因为Java里面没有更小的类型了），又想到可以用一个数字的每一位来存0/1就不需要数组了。但最大的long也只有64位，题目当中的n最大是104.需要105个位置。

当前题解空间复杂度达到了n.满足不了进阶的要求。

题解二

什么方法可以在当前给出的数组内部直接得到缺失谁呢。

一段连续的数字堆在一起，只少一个...连续的数字？

求和...对就是求和，0到n的数字的和减去当前数组所有元素的和，差是多少就是多出来的数字。

// 0到n数字的和
(1+n) * n / 2

代码：

public int missingNumber(int[] nums) {
    int len = nums.length;
    int expect = (1 + len) * len / 2;
    for(int i = 0; i < len; i++){
        // 减去每个数字
        expect -= nums[i];
    }
    return expect;
}

题解三

虽然解出了觉得比较满意的答案，但确实有预感是有更好的解法，从0到n连续的数字索引就是它们的值没必要额外去存储记录什么，可能性潜藏的已知条件太多了很有可能没有用上。

缺少一个数字的数组和原来的完整的n + 1的数字。合在一起就是一堆数字每个都是一对且只有一个落单，这么一堆数字进行累计异或最终双双相消就可以得到唯一的数字。

我们不需要额外的去创建一个这样的合成数组，因为数字和下标一一对应，循环一次0到n即可得到原来的这些数字进行异或，再对提供的数组进行异或即可。

public int missingNumber(int[] nums) {
    int res = 0;
    for (int i = 0; i <= nums.length; i++){
        res ^= i;
    } 
    for (int i : nums) {
        res ^= i;
    }
    return res;
}

总结

这题是当前合集最后一个分类其他也是最后一题但它的类型偏向与数组，可以回顾数组的一些常规操作比如排序、哈希、原地交换等将原本数组进行整理得到新数组的手段.

异或题解参考了官方解题，想到了自己的曾经的总结异或运算找唯一，却在此题没有自主发现。没有充分的利用已知的数列与参数数组的关系。这和2020年9月21号解的只出现一次的元素异曲同工。

初级合集全部题解到此就完结了，原计划半年到现在两年了才完成，太过于懈怠了。合集过后对数组、链表以及树从生疏到现在确实有了更多的了解再次面对时充满了更多的思路。但数据结构仍有待加强，算法思想需体系学习。因此不会立马开启下一合集的题解系列，第一是有其他方向的内容需要学习和输出，第二是在算法这边开始进行系统的学习输入希望日后可以带来更好的内容。

往期推荐

198 打家劫舍

384 打乱数组

155 最小栈

104 二叉树最大深度