268. Missing Number

problem description

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

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

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

algorithm thought

开始看到这题，感觉很像前面一个题目，于是用了类似的做法。首先将vector转为unordered_set，这里时间复杂度是O(n)，然后再count中找到missing number。时间复杂度也是O(n)。

但是运行出来却很慢，看了discuss之后，发现可以直接用异或解题。因为这里数字是从0开始，下标也是从0开始。对应起来就是下标和数组加到一起，每个都必须出现两次。如果有一个值出现一次，那最后要返回他。是不是很像single number。直接将所有数异或起来就行。

code

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

algorithm analysis

时间复杂度O(n)