【力扣刷题实战】丢失的数字

大家好，我是小卡皮巴拉

文章目录

目录

力扣题目：丢失的数字

题目描述

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C++）

兄弟们共勉 ！！！ 

---

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目：丢失的数字

原题链接：268. 丢失的数字 - 力扣（LeetCode）

题目描述

给定一个包含 [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 中。

提示：

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

解题思路

问题理解

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

算法选择

采用异或（XOR）操作的方法。异或操作有一个特性：一个数与自身异或结果为 0，一个数与 0 异或结果为其本身。利用这个特性，对数组中的元素和 [0, n] 范围内的所有数进行异或操作，最终得到的结果就是缺失的数字。

具体思路

1. 初始化：定义变量 ret 并初始化为 0，用于存储异或操作的结果。

2. 对数组元素进行异或操作：使用 for 循环遍历数组 nums，对于数组中的每个元素 x，将 ret 与 x 进行异或操作（ret ^= x）。这样，ret 就记录了数组中所有元素的异或结果。

3. 对 [0, n] 范围内的数进行异或操作：使用另一个 for 循环，从 0 到数组 nums 的大小（包含数组大小）遍历所有整数 i。对于每个 i，将 ret 与 i 进行异或操作（ret ^= i）。

   • 在这个过程中，数组中出现的数字会在与 [0, n] 范围内的对应数字进行异或时相互抵消（因为一个数与自身异或结果为 0）。

   • 而缺失的数字由于在数组中不存在，不会被抵消，最终 ret 的值就是这个缺失的数字。

4. 返回结果：循环结束后，ret 中存储的就是在 [0, n] 范围内没有出现在数组 nums 中的那个数，返回 ret。

解题要点

1. 异或操作特性的运用：熟练掌握异或操作的特性，即一个数与自身异或结果为 0，一个数与 0 异或结果为其本身。利用这个特性来抵消数组中已出现的数字，从而找出缺失的数字。

2. 两次异或操作的顺序：先对数组中的元素进行异或操作，再对 [0, n] 范围内的数进行异或操作，顺序不能颠倒，这样才能保证最终得到正确的结果。

3. 范围的处理：注意循环的范围是从 0 到数组 nums 的大小（包含数组大小），确保涵盖了 [0, n] 范围内的所有数，以便找出缺失的数字。

完整代码（C++）

class Solution {
public:int missingNumber(vector<int>& nums) {// 初始化结果变量 ret 为 0，用于通过异或操作来找出缺失的数字int ret = 0;// 遍历数组 nums，对数组中的每个元素 x 与 ret 进行异或操作for(auto x : nums) ret ^= x;// 遍历从 0 到数组 nums 的大小（包含数组大小）的所有整数 ifor(int i = 0; i <= nums.size(); i++){// 将 i 与 ret 进行异或操作ret ^= i;}// 最终 ret 的值就是在 [0, n] 范围内没有出现在数组 nums 中的那个数，返回 retreturn ret;}
};

兄弟们共勉 ！！！ 

码字不易，求个三连

抱拳了兄弟们！