数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。
你有办法在O(n)时间内完成吗？
注意：本题相对书上原题稍作改动
示例 1：
输入：[3,0,1]
输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8
🐢思路 1：冒泡遍历🐢
1.冒泡排序
2.遍历，如果当前值+1，不等于下一个数字就是下一个数
此时时复杂度为O(N^2)
int missingNumber(int* nums, int numsSize) { int cout=0,temp = 0,i; for (i = 0; i < numsSize-1; i++) { for (int j = 0; j < numsSize -1- i; j++) { if (nums[j] > nums[j+1]) { temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; cout = 1; } } if (cout == 0) break; } for (i = 0; i < numsSize-1; i++) { if ((nums[i] + 1) != nums[i + 1]) { return nums[i] + 1; } } }
🦒思路 2：单身狗 异或思想:🦒
res = res ^ x ^ x。对同一个值异或两次，那么结果等于它本身
例如：输入：[9,6,4,2,3,5,7,0,1]
输出：8
我们重新创建一个数组[0.1.2.3.4.5.6.7.8.9]与所求数组[9,6,4,2,3,5,7,0,1]进行异或，
剩下的数字就是缺失的整数。 F(N)=2N-1;
时间复杂度为O(N).
int missingNumber(int* nums, int numsSize) { int ret=0; for(int i=0;i<numsSize;i++) { ret^=nums[i]; } for(int i=0;i<=numsSize;i++) { ret^=i; } return ret;
🦋思路 3：和差法🦋
1.0—n 等差数列计算和；
2.依次减掉数据中的值，剩下的就是消失的数字.F(N)=N-1
时间复杂度为O(N).
int missingNumber(int* nums, int numsSize) { int N=numsSize; int sum=((0+N)*(N+1))/2; for (int i=0;i<numsSize;i++) { sum-=nums[i]; } return sum; }
