【LeetCode面试题17.04】消失的数字

Ne0inhk

— 5 min read
【LeetCode面试题17.04】消失的数字

刷爆LeetCode系列

LeetCode面试题17.04：消失的数字

github地址

有梦想的电信狗

前言

本文用C++三种方法实现LeetCode面试题17.04：消失的数字

  • 方法一：数组哈希
  • 方法二：数学求和再相减
  • 方法三：位运算

题目描述

题目链接：https://leetcode.cn/problems/missing-number-lcci/description/

在这里插入图片描述

题目与思路分析

目标分析

  1. 数组nums包含从0到n的所有整数，但其中缺了一个。编写代码找出那个缺失的数字
  2. 要求时间复杂度至多为O(n)

思路一：数组哈希

思想：

  • 题目给出一个长度为 n 的数组，元素取值范围为 0 ~ n，且恰好缺失一个数。
  • 新建一个长度为 n + 1 的辅助数组 v，下标表示数字本身，值表示是否出现过。
  • 遍历原数组，将出现过的数字对应位置标记为 1。
  • 再遍历辅助数组，第一个为 0 的下标就是缺失的数字。

注意事项：

  • 辅助数组长度必须是 nums.size() + 1，否则无法覆盖 n。
  • 访问 v[nums[i]] 前要保证 nums[i] 一定在 0 ~ n 范围内。
  • 时间复杂度为 O(n)，空间复杂度为 O(n)。

思路二：数学求和

思想：

  • 如果 0 ~ n 没有缺失，总和应为：
    t o t a l = n ( n + 1 ) 2 total = \frac{n(n+1)}{2} total=2n(n+1)​
  • 实际数组的元素之和记为 sum。
  • 由于只缺失一个数，那么
    m i s s i n g = S − s u m missing = S - sum missing=S−sum
  • 一次遍历即可算出答案。

注意事项：

  • n = nums.size()，而不是数组中最大值。
  • 使用 int 时要注意是否可能溢出（本题数据范围安全）。
  • 时间复杂度 O(n)，空间复杂度 O(1)。

思路三：位运算（异或）

思想：

  • 异或的性质：
    • a ^ a = 0
    • a ^ 0 = a
  • 数组中包含 0 ~ n 缺一个数，共 n 个数。
  • 将数组中所有元素互相异或，再将 0 ~ n 全部互相异或：
    • 出现两次的数字会互相抵消为 0
    • 只出现一次的那个数字（缺失值）会被保留下来
  • 最终的异或结果就是缺失的数。

注意事项：

  • 第二个循环必须遍历 0 ~ n（即 i <= nums.size()）。
  • 异或不会产生溢出问题，适合大范围整数。
  • 时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

思路一：数组哈希

// 数组哈希classSolution{public:intmissingNumber(vector<int>& nums){// 0-n 共 n+1 个数，缺了一个，还剩 n 个// 开一个大小为n+1 的数组，初始化值均为0// 遍历 这n个数，将其对应下标的位置标记为 1// 再遍历这个数组，值为0的位置的下标，就是缺失的数 vector<int>v(nums.size()+1,0);for(auto e:nums){ v[e]=1;}int i =0;for(;i< v.size();++i){if(v[i]==0)break;}return i;}};

思路二：数学求和

// 求和classSolution{public:intmissingNumber(vector<int>& nums){// 0-n 这些数 正确的和 为 totalint total = nums.size()*(nums.size()+1)/2;int sum =0;// 缺了一个数后的和 为 sumfor(auto e:nums) sum += e;return total - sum;// 相差的值 即为 缺失的数字}};

思路三：位运算

// 位运算classSolution{public:intmissingNumber(vector<int>& nums){// 数组中有 0-n 缺了一个，共 n 个数，再在后面添加 0 - n 这完全不缺 的 n + 1 个数// 则共有 2n+1 个数 2n+1个数中，消失的数只出现了一次// 其他数，每个数都出现了两次// 一个数 和0 异或 等于它本身 一个数 和 它本身异或 等于 0int res =0;for(int i =0;i<nums.size();++i) res ^= nums[i];for(int i =0;i<=nums.size();++i) res ^= i;return res;}};

算法代码优化

  • 可以选择使用STL自带的哈希容器优化，但非必须
  • 其他方法无需优化
classSolution{public:intmissingNumber(vector<int>& nums){ unordered_set<int> set;// 将这 n 个数 插入到 哈希setfor(auto e : nums){ set.insert(e);}int missing =-1;// 再遍历数字 0-n 那个数字没有出现，就是缺失的数字for(int i =0; i <= nums.size(); i++){if(set.count(i)==0){ missing = i;break;}}return missing;}};

结语

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！征程尚未结束，让我们在广阔的世界里继续前行！ 🚀

Read more