题目：
消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O（n）时间内完成吗？
示例：
输入【3，0，1】
输出：2
解答：
想法1：先排序后查找
但一个排序耗费的时间就不符合O（n）,最快的排序O（n*logn）。（注意二分查找的基础是已经排好序的数组!）
想法2：相加再相减
把0~N加到一起再减去数组中的数，即可求得，并且时间复杂度就是O（n）
源码：
#include<iostream> using namespace std; int main() { int num[6] = { 3,6,4,1,5 }; int sum1 = 0; int sum2 = 0; for (int i=1;i<=6;i++) { sum1 += i; } for (int i=0;i<5;i++) { sum2 += num[i]; } cout << sum1 - sum2 << endl; return 0; }
想法3：异或处理（O（n））
^对二进制位进行计算，
^的一些重要性质：
- 相同为0，相异为1.
- 0跟任何数^都为那个数本身（这个性质可以把0看成桥梁！）
- 两个相同的数进行异或，结果就是0
- 异或满足结合律和交换律。
我们无法将两个数组同时进行异或，但我们可以用0先跟第一个数组异或，然后用这个结果与另外一个数组进行异或，效果相同！
源码：
int main() { int num[5] = { 1,2,5,4 }; int a = 0; for (int i=0;i<4;i++) { a ^= num[i]; } for (int i=1;i<=5;i++) { a ^= i; } cout << a << endl; return 0; }
