268. Missing Number

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?

 

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        //bitmap法:数组中所有数其实是0----n序列n个数（缺一个）,其中缺的数用n来替代了
        int result = nums.size();
        //0 1 3
        for(int i=0;i<nums.size();i++){
            result ^= nums[i];
            result ^= i;
        }
        return result;
    }
};

//法二求和

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        //求和公式 s = n*(n+1)/2
        int n=nums.size();
        //正常序列0--n+1的和 0 1 2 3
        int sumComm = (n)*(n+1)/2;
        //原数组0---n+1缺一个的和
        int sum=0;
        for(int i=0;i<n;i++){
            sum += nums[i];
        }
        return sumComm -sum;
    }
};