力扣--268丢失的数字（三种解法）
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 解法1
- 解法2
- 解法3
给定一个包含 [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;//返回丢失的数字}}
优点：这种解法简单，只需要循环嵌套即可
缺点：时间复杂度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;
}
这种解法很好，时间复杂度在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;
这种解法很好，就是有点难想到，时间复杂度为O(n)
总结
相比于第一种后面的两种在时间上有优势，但是后面两种有点难想到，特别是第三种
今天的分享就到这里了，谢谢大家的观看