力扣--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 中。

题目已经清楚的说明了，要我们找到[ 0 n]中数组每出现的数字

解法1

大家看到题的时候的第一想法就是循环嵌套吧，通过遍历来找到那个数字。
好，那么我们就来实现一下

int missingNumber(int* nums, int numsSize) {
	for (int i = 0; i <= numsSize; i++) {//第一个循环，将[1~n]的数字遍历一次
		int t=0;//标志变量
		for (int j =0 ; j < numsSize; j++) {//在数组中寻找i找不到就是的话就是丢失的数字
			if (nums[j] == i)
			{
				t = 1;//找到i就是t=1加打破
				break;
			}
		}
		if (t == 0)
			return i;//返回丢失的数字
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

优点：这种解法简单，只需要循环嵌套即可
缺点：时间复杂度O(n*n),时间过长可能超过时限

解法2

我们要注意一个点就是这些数字是[ 0 n]且数组数字不重复，那么我们可以将0~n都加起来然后再减去数组中的所有数字，得到的就是丢失的数字了
实现：

int missingNumber(int* nums, int numsSize) {
    int r=0;
    for(int i=1;i<=numsSize;i++)//将0-n的数字都加起来
          r=r+i;     
    for(int i=0;i<numsSize;i++)
    r=r-nums[i];减去数组中所有的数字
    return r;
}
1
2
3
4
5
6
7
8

这种解法很好，时间复杂度在O（n），也很容易实现

解法3

第三种方法就是利用异或了

异或有两个性质
1.0和任何一个数异或都等于那个数
2.相同的数字异或的结果为0

我们可以设置一个数为0，再和[0-n]的数字异或，之后再和数组的各个元素异或，这样一来相同的数字就被抵消了，剩下0和丢失的那个数，又因为0和任何一个数异或都等于那个数，所以最后得到的数就是丢失的数字了
实现：

int missingNumber(int* nums, int numsSize) {
    int r = 0;
    for (int i = 1; i <= numsSize; i++)//让r和0-n的数字都异或
        r = r ^ i;
    for (int i = 0; i < numsSize; i++)//再和数组中的所有元素异或，最终就是丢失的数字了
        r = r ^ nums[i];
    return r;
1
2
3
4
5
6
7

这种解法很好，就是有点难想到，时间复杂度为O(n)

总结

相比于第一种后面的两种在时间上有优势，但是后面两种有点难想到，特别是第三种

今天的分享就到这里了，谢谢大家的观看