1. 题目分析

数组 nums 包含从 0 到 n 的所有整数，但其中缺了一个。

请编写代码找出那个缺失的整数。你有办法在

(

)

O(n)

$O (n)$ 时间内完成吗？

示例 1：

示例 2：

2. 题目图解

分析思路之前首先要记住：

数组 nums 是从 0 到 n 开始的，假设数组长度是 5，那么 nums 里面本来的元素就是 0 到 5；

🍑 思路一：排序

首先输入一组数据，如图所示👇

因为题目说的是，数组包含 0 到 n 的所有整数，没有说这些数字是有序的，那么我们可以先对数组进行排序，如图所示👇

排完序以后，我们就直接遍历整个数组，看后一个值是不是由 前一个加 1 得来的；

也就是说，当我们遍历到 7 的时候，本来后面一个值应该是 8，但此时后一个值是 9，那么缺的那个值就是 8，如图所示👇

如果用 冒泡排序 的话，那么时间复杂度就是

O

(

N

2

)

O(N^2)

$O (N^{2})$ ；

如果用 快速排序 的话，那么时间复杂度就是

O

(

N

∗

l

o

g

N

)

O(N*log^N)

$O (N * l o g^{N})$

时间复杂度都不满足题目要求，所以这道题不能使用排序。

🍑 思路二：映射

我们还是假设输入 [9，6，4，2，3，5，7，0，1] 这组数据。这组数据是包含了 0 到 10 的数组，但是缺少了数字 8。

然后遍历输入的数组 [9，6，4，2，3，5，7，0，1] 里面的每个值，比如第一个元素为 9，那么就在开辟的新数组的下标为 9 的位置里面写成 9；

第二个元素为 6，那么把 6 放在新数组里面下标为 6 的位置，以此类推…

首先我们开辟一个下标为 0 到 10 的数组，然后把每个下标对应的元素都初始化为 -1，如图所示👇

每个值是多少，就放在下标对应是位置去，如图所示👇

然后我们再把新开辟的数组遍历一遍，发现下标为 8 的位置里面的元素还是 -1，那说明缺的数字就是 8。

这种方法的时间复杂度是：

O

(

N

)

O(N)

$O (N)$ ，说明是符合题意的。

但是这种方式有个缺陷，那就是空间复杂度也为

O

(

N

)

O(N)

$O (N)$ ，

🍑 思路三：异或

思路：用一个数字 val 跟 0 到 n 的数字异或，再跟缺失的数组 nums 异或。

什么意思呢？首先记住异或的特点：参与运算的两个值，如果两个值相同，则结果为0，否则为1。

（1） 0 ^ 0 = 0，0 ^ 1 = 1，则0 异或任何数＝任何数；

（2） 1 ^ 0 = 1，1 ^ 1 = 0，则 1 异或任何数 = 任何数取反；

（3）任何数异或自己＝把自己置 0；

假设还是上面的数组：[9，6，4，2，3，5，7，0，1]，首先把 val 置为 0，让它去异或 0 到 9（此时的 n 为 9） ，然后再跟数组 [9，6，4，2，3，5，7，0，1] 里面的每个值去异或，如图所示👇

因为我们知道 任何数异或自己等于 0，并且 0 异或任何数等于任何数；

所以我们可以把相同的异或掉，那么就还剩下数字 0 和数字 8 没有异或，它们异或的结果就是缺失的元素 8，如图所示👇

那么这种思路只遍历了一遍，所以时间复杂度是：

O

(

N

)

O(N)

$O (N)$

🍑 思路四：等差数列公式

因为题中说了数组包含 0 到 n 的所有整数，而且数组的长度也给了的，是 numSize；

那么直接用 等差数列求和 公式计算：1 到 numSize 的总和，然后再减去 缺失的数组 中的每个元素，那么剩下的就是缺的数字

等差数列求和公式：

n

(

n

+

1

)

/

2

n(n+1)/2

$n (n + 1) /2$

这种方法只把数组遍历一遍，所以时间复杂度是：

O

(

N

)

O(N)

$O (N)$

3. 代码实现

🍑 异或实现

📝 接口代码

int missingNumber(int* nums, int numsSize){
    int val = 0;
    int i = 0;
    // 用val去异或[0,numsSize]间的所有数字
    for (i = 0; i <= numsSize; ++i) {
        val ^= i;
    }
    
    // 然后再把结果去异或nums数组的数字
    for (i = 0; i < numsSize; ++i) {
        val ^= nums[i];
    }
    
    return val;
}

🍑 等差数列实现

📝 接口代码

int missingNumber(int* nums, int numsSize){
    int sum = numsSize * (numsSize + 1) / 2;
    for (int i = 0; i < numsSize; ++i) {
        sum -= nums[i];
    }
    return sum;
}