寻找缺失的数

给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。

 

您在真实的面试中是否遇到过这个题？

Yes

样例

N = 4 且序列为 [0, 1, 3] 时，缺失的数为2。

注意

可以改变序列中数的位置。

挑战

在数组上原地完成，使用O(1)的额外空间和O(N)的时间。

 

 

嗯。。 用一个int 保存结果，初值设为0，之后将每个int的值和下标和结果变量异或就好。

位运算好久没用过了，这还是去百度了才想起来。。。

1 class Solution { 2 public: 3     /**     4      * @param nums: a vector of integers 5      * @return: an integer 6      */ 7     int findMissing(vector
         
           &nums) { 8         // write your code here 9         vector
          
           ::iterator it;10         int a = 0;11         int i = 0;12         for(it = nums.begin();it != nums.end();it++) {13             a ^= (i+1)^(*it);14             i++;15         }16         return a;17     }18 };