前言
我有我要赶去的远方，风雨兼程披星戴月
本章的内容是力扣每日随机一题的部分方法的解析
提示：以下是本篇文章正文内容，下面案例可供参考
面试题17.04.消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。在O(n)时间内完成
方法一：
*先排序(用qsort函数排序),依次查找，如果下一个数不是上一个数+1，那么上一个数+1就是消失的数字；
不过这个方法并不符合O(n)；
#include<stdio.h> int cmp_int(void* p1, void* p2) { return *(int*)p1 - *(int*)p2; } int main() { int nums[9] = { 2,3,1,4,6,7,9,10,8 }; int numsSize = sizeof(nums) / sizeof(nums[0]); qsort(nums, numsSize, sizeof(nums[0]), cmp_int); int i = 0; /*for (i = 0; i < numsSize; i++) { printf("%d ", nums[i]); }*/ int x = 0; while (nums[i]) { if (nums[i] + 1 != nums[i + 1]) { x = nums[i]+1; break; } else { i++; } } printf("%d\n", x); return 0; }
方法二：
采用异或思路：先将数组中所有的数异或在一起，然后赋值给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,今天的力扣每日一题内容就到此结束啦，如果后续想了解更多，就请关注我吧。
