class Solution 
{
public:
    int missingNumber(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end()); //排序
        int n = nums.size();
        for (int i = 0; i < n; ++i) 
        {
            if (nums[i] != i) //第一种情况
            return i;
        }
        return n;  //第二种情况
    } 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第二种方法:哈希集合

本质上是和第一种方法一样的,只是降低了复杂度
首先遍历数组 nums，将数组中的每个元素加入哈希集合，然后依次检查从 0 到 n 的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。
代码如下:

class Solution 
{
public:
    int missingNumber(vector<int>& nums) 
    {
        unordered_set<int> set;
        int n = nums.size();
        for (int i = 0; i < n; ++i) //将存在的元素都存入集合
        set.insert(nums[i]);

        int missing = -1; //因为0也是元素,所以初始化为-1
        for (int i = 0; i <= n; ++i) //检查0~n的元素
        {
            if (!set.count(i)) //看哪个元素不在set中
            {
                missing = i;   //缺失的就是这个元素
                break;
            }
        }
        return missing;
    }
   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第三种方法:位运算!

这种方法的原理和leetcode-136.只出现一次的数字一样,可以点进去看一下
核心思想就是:一个数和它自己异或运算就会抵消掉归零
我们只需将所有元素和下标进行异或运算,最后留下来的即为找不到元素的下标

class Solution 
{
public:
    int missingNumber(vector<int>& nums) 
    {
        int res = 0, n = nums.size();

        for (int i = 0; i < n; ++i) //异或元素
        res ^= nums[i];

        for (int i = 0; i <= n; ++i) //异或下标
        res ^= i;
    /*也可以简写为:
    for (int i = 0; i < n; ++i)
    {
        res ^= nums[i];
        res ^= i;
    }
    这种方法需要注意的点是需要注意循环i取不到n
    所以res要初始化为n
    */
        return res;
    }
   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

第四种方法:数学方法

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

        return total - arrSum;

    }
   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

位运算常用技巧