Day 31 - 268.missing number

Day31 - 268.丢失的数字

LeetCode 268.丢失的数字

题目链接：

https://leetcode.cn/problems/missing-number/

1. 题目描述

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

举个例子：

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

2. 思路解析

2.1. 方法零 直接查找

先对数组进行排序，使得下标和元素之间具有一定的逻辑关系。

直接利用下标的逻辑关系查找。

2.2. C++代码

class Solution
{
public:
    int missingNumber(vector<int> &nums)
    {
        int nums_len = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums_len; i++)
        {
            // 如果找不到某个数字，就返回当前在找的数字
            // 即循环变量 i
            if(nums[i] != i)
            {
                return i;
            }
        }
        return nums_len;
    }
};

如果for循环内的元素都找到了，那么题目可以确定必然有缺失的元素。但是由于数组的边界，不能遍历完全，直接返回数的大小即可

这种方法需要对数组进行排序，排序的复杂度为 ，遍历的复杂度 ，最后的复杂度也是 。

下面两个办法可以避免排序，降复杂度为

2.3. 方法一 位运算

首先来看一下异或运算的特点，11转成二进制1011，13转成二进制1101，它们之间的异或运算如下图：

11 ^ 13 = 6，11 ^ 11 = 0，可以看出，对于二进制相同的bit位按位异或值是0，比如1 ^ 1 = 0，0 ^ 0 = 0。不同值bit位按位异或值是1，比如1 ^ 0 = 1。

利用异或运算符这个特性我们可以轻松解决这个题目。

对区间[0, n]和数组nums中所有的元素做异或运算，在nums中的元素会出现两次，不在nums中的元素只会出现一次，两个相同的元素做异或值为0，最后的结果就是不在nums中的元素。

比如n = 3，nums = [3, 0, 1]。0 ^ 1 ^ 2 ^ 3 ^ 3 ^ 0 ^ 1 = (0 ^ 0) ^ (1 ^ 1) ^ (3 ^ 3) ^ 2 = 0 ^ 2 = 2。最终2就是不在nums中的数字。

2.4. C++代码

class Solution
{
public:
    int missingNumber(vector<int> &nums)
    {
        int nums_len = nums.size();
        // 由于循环内的 i 变量没有办法取到 nums_len
        // 可以先赋 nums_len 给 res
        int res = nums_len;
        for (int i = 0; i < nums_len; i++)
        {
            // 连续异或运算
            res = res ^ (nums[i] ^ i);
        }
        // 最后运算的结果就是丢失的数字
        return res;
    }
};

2.5. 方法二 数学运算

因为区间[0, n]上有n + 1个元素，数组nums中只有n个元素，假设缺失的元素为X，我们可以得到如下公式：

我们只需要用区间[0, n]所有元素的和减去nums中所有元素的和就得到最终的结果X。

2.6. C++代码

class Solution
{
public:
    int missingNumber(vector<int> &nums)
    {
        int nums_len = nums.size();
        // 由于循环内的 i 变量没有办法取到 nums_len
        // 可以先赋 nums_len 给 res
        int res = nums_len;
        for (int i = 0; i < nums_len; i++)
        {
            // 连续加运算
            res = res + i - nums[i];
        }
        // 最后运算的结果就是丢失的数字
        return res;
    }
};

3. 复杂度分析

时间复杂度： 后两种方法的整个过程都是只遍历了一遍数组，所以时间复杂度为O(n)，n为数组nums的长度。

空间复杂度： 后两种方法都只使用了几个整型变量，所以空间复杂度都是O(1)。

4. Redo. 02/14

久违的刷题了，修生养息三天恢复训练了，题目还是要坚持刷...不然算法忘记得真的快啊...

哈希集合

class Solution
{
public:
    int missingNumber(vector<int> &nums)
    {
        int nums_len = nums.size();
        int res;
        unordered_set<int> u_set;
        for(int i = 0; i < nums_len; i++)
        {
            u_set.emplace(nums[i]);
        }

        for(int i = 0; i <= nums_len; i++)
        {
            if(u_set.find(i) == u_set.end())
            {
                res = i;
            }
        }

        return res;
    }
};

异或操作

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

加和操作

class Solution
{
public:
    int missingNumber(vector<int> &nums)
    {
        int nums_len = nums.size();
        int res = 0;
        for (int i = 0; i < nums_len; i++)
        {
            res = res - nums[i];
        }
        for (int i = 0; i <= nums_len; i++)
        {
            res = res + i;
        }
        return res;
        
    }
};