268. Missing Number

Total Accepted: 31740 

Total Submissions: 83547 

Difficulty: Medium

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,

Given nums = [0, 1, 3] return 2.

Note:

Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

分析：DONE

我真蛋疼。题意理解错了，我还以为是干嘛呢！

后来才明确原来是随机从0到size()选取了n个数，当中仅仅有一个丢失了（显然的）。

别人的算法：数学推出，0到size()的总和减去当前数组和sum

class Solution {public:    int missingNumber(vector
     
      & nums) {        int sum = 0;          for(int num: nums)            sum += num;          int n = nums.size();          return (n * (n + 1))/ 2 - sum;      }};
     

这道问题被标注为位运算问题：參考讨论区的位运算解法：

这个异或运算曾经用到过，到这道题还是想不起这种方法，我真是日了狗了！

异或运算xor。

0 ^ a = a ^ 0 =a

a ^ b = b ^ a

a ^ a = 0

0到size（）间的全部数一起与数组中的数进行异或运算，

由于同则0,0异或某个未出现的数将存活下来

class Solution {public:    int missingNumber(vector
     
      & nums) {        int res = 0;        for (int i = 1; i <= nums.size(); i++)             res =res ^ i ^ nums[i-1];         return res;     }};
     

注：本博文为原创，兴许可能继续更新本文。

假设转载，请务必复制本条信息！

原文地址：http://blog.csdn.net/ebowtang/article/details/50457902

原作者博客：http://blog.csdn.net/ebowtang