missingNumber.cpp

#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

class SolutionOn
{
public:
    int missingNumber(vector<int> &nums)
    {
        sort(nums.begin(),nums.end());
        int arraylength = nums.size();
        int res = -1;

        for(int i = 0;i < arraylength;i++)
        {
            if (nums[i] != i)
            {
                res = i;
                break;
            } 
        }
        if (res == -1) return arraylength;
        
        return res;
    }
};

class SolutionXOR
{
public:
    // 使用异或进行运算，速度快
    // 我们使用的原理是：相同数字异或为0，不同为其他数，利用这个判断
    int missingNumber(vector<int> &nums)
    {
        int res = nums.size();
        for (int i = 0;i < nums.size();i++)
        {
            // i ^ nums[i]，如果相同，那么就是0，与res进行异或，还是它本身
            // 条件给出来了，只有一个缺的数字，所以一定能找出来哪一个缺的
            // 其他都还是保持res本身，毕竟都一样
            res ^= i ^ nums[i];
        }

        return res;
    }
};

class Solution
{
public:
    int missingNumber(vector<int> &nums)
    {
        int result = nums.size();
        unordered_set<int> res;
        for (auto num : nums)
        {
            res.insert(num);
        }

        for (int i = 0;i < nums.size();i++)
        {
            // 没找到这个，说明没有
            if (res.find(i) == res.end())
            {
                result = i;
                break;
            }
        }

        return result;
    }
};