【算法 | 位运算No.1】leetcode268. 丢失的数字

àì夳堔傛蜴生んèń 2024-04-27 06:40 12阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[Leetcode][]】  
> 🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> 🍓希望我们一起努力、成长，共同进步。

[点击直接跳转到该题目][Link 3]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣题目解析
 *  3️⃣解题代码

## 1️⃣题目描述 ##

给定一个包含 `[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 = \[0,1\]  
> 输出：2  
> 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 \[0,2\] 内。2 是丢失的数字，因为它没有出现在 nums 中。

**示例4：**

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

**注意：**

*  `n == nums.length`
 *  `1 <= n <= 104`
 *  `0 <= nums[i] <= n`
 *  `nums 中的所有数字都 独一无二`

## 2️⃣题目解析 ##

总共有三种解法（**哈希、位运算、高斯求和**）。

这里只对`位运算`和`高斯求和`进行解释。

**位运算求解原理：**

*  **`相同数组进行异或结果为0`**
 *  `0 ^ num = num`

**高斯求和原理：**

*  **把\[0,n\]的和记为`sum1`**
 *  **把数组nums中所有的元素之和记为`sum2`**
 *  **丢失的数字即为`sum1 - sum2`**

## 3️⃣解题代码 ##

**解法1（`高斯求和`）：**

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

**解法2（`位运算`）：**

class Solution {
        
    public:
        int missingNumber(vector<int>& nums) {
        
            int n = nums.size(),ret = 0;
            for(auto x : nums) ret ^= x;
            for(int i = 0;i <= n;i++) ret ^= i;
            return ret;
        }
    };

![在这里插入图片描述][2df9e76ee76f4f98b81738f91280fc8e.png]

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[Leetcode]: https://blog.csdn.net/m0_74352571/category_12252087.html?spm=1001.2014.3001.5482
[Link 3]: https://leetcode.cn/problems/missing-number/description/
[2df9e76ee76f4f98b81738f91280fc8e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/8db8cd700ce14ac58ebe094f3d978779.png