每日一题：12. 丢失的数字（C++）

题目：
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

例：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

解题思路（哈希）：

1. 利用bool动态数组，长度为给出数组长度加上一（[0,n]多出个数字）
2. 把数组中所有数字作为下标赋值为true,剩下的一个值为false的下标便是多出来的数组
   代码

class Solution {
public:
    int missingNumber(vector& nums) {
        bool* temp_nums = new bool[nums.size() + 1]();
        for(int i : nums) {temp_nums[i] = true;}
        for(int i = 0; i <= nums.size(); i++){
if(!temp_nums[i]){return i;}
}
        return 0;
    }
};

解题思路（异或）：

1. 根据 x ^ x = 0; 0 ^ x = x异或运算规律
2. 将[0,n]进行异或，再将结果与给出的数组所有数字进行异或，得到多出数字
   代码

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

解题思路（数学）：

1. 利用数学等差数列求和：

2. 再减去给出数组所有数字之合，得到多出数字
   代码

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

解题思路（排序）：

1. 将给出数组进行排序
2. 遍历[0,n]所有数字，与数组从头开始进行一一比较，不同则为多出数字
   代码

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

作者：yi-si-cb
链接：https://leetcode-cn.com/problems/missing-number/solution/xie-shi-jian-dan-si-jie-c-by-yi-si-cb-nbce/