LeetCode 268. Missing Number

三种方法
1、异或操作。
因为两个相同的数异或之后等于零，所以将数组与0到n异或，最后剩下的那个数就是数组中缺失的数。

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

2.求和操作。
求出0到n的和，分别减去数组中已有的数，最后结果就是数组中缺失的数。

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

3、排序比较
对数组排序，然后将数组元素与所对应下标比较，第一个不相等的下标，即是数组缺失的数。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] != i){
                n = i;
                break;
            }
        }
        return n;
    }
};