前言

我有我要赶去的远方，风雨兼程披星戴月
本章的内容是力扣每日随机一题的部分方法的解析

提示：以下是本篇文章正文内容，下面案例可供参考

面试题17.04.消失的数字

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。在O(n)时间内完成

方法一：

先排序(用qsort函数排序),依次查找，如果下一个数不是上一个数+1，那么上一个数+1就是消失的数字；
不过这个方法并不符合O(n)而是O(nlogn）；

方法二：

采用异或思路：先将数组中所有的数异或在一起，然后赋值给x，再将x与(0-n)异或起来得到的数字就是消失的数字，这种方法是O(n)符合要求

int missingNumber(int* nums, int numsSize)
{int i=0;int x=0;for(i=0;i<numsSize;i++){x=x^nums[i];}for(i=0;i<numsSize+1;i++)//注意这里一定要+1因为numsSize是数组中元素个数，它消失了一个数字所以其实应该是numsSize+1{x^=i;}return x;
}

异或解析：

1.1 运算规则

相同为0，不同为1，即
1 ^ 1 = 0
0 ^ 0 = 0
1 ^ 0 = 1
由运算规则可知，任何二进制数与零异或，都会等于其本身，即 A ^ 0 = A。

1.2 异或性质

（1）交换律： A ^ B = B ^ A

（2）结合律： ( A ^ B ) ^ C = A ^ ( B ^ C )

（3）自反性： A ^ B ^ B = A （由结合律可推： A ^ B ^ B = A ^ ( B ^ B ) = A ^ 0 = A）

方法三：

将0~n中所有的数字加在一起(一个等差数列公式计算)，得到一个数然后减去数组中的数字，最后得到的就是消失的那个数字，这种方法是O(n)也符合要求

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

总结

Ending,今天的力扣每日一题内容就到此结束啦，如果后续想了解更多，就请关注我吧，一键三连，还有许多种方法没有写出希望各位佬补充哦~