位运算

题目详情

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

示例1：

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

示例2:

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

示例3:

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

示例4:

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

第一种方法:排序比较元素和下标

我们可以将数组排序,存在的数字,将会与它的下标相对应
数组长n,下标为[0,n-1],假设缺失的数字为k,那么存在下面两种情况:
<1> 0≤k<n : 此时缺失的元素前面的元素和下标都一一对应,到了k变为nums[k] == k+1
<2> k == n : 此时0~n-1没有缺失的,所以对于任意nums[i]都是nums[i] == i,即元素和下标一一对应
代码如下:

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;  //第二种情况
    } 
};

第二种方法:哈希集合

本质上是和第一种方法一样的,只是降低了复杂度
首先遍历数组 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;
    }
   
};

第三种方法:位运算!

这种方法的原理和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;
    }
   
};

第四种方法:数学方法

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;

    }
   
};

位运算常用技巧