【LeetCode面试题17.04】消失的数字
刷爆LeetCode系列
LeetCode面试题17.04：消失的数字
github地址
前言
本文用C++三种方法实现LeetCode面试题17.04：消失的数字
- 方法一：数组哈希
- 方法二：数学求和再相减
- 方法三：位运算
题目描述
题目链接：https://leetcode.cn/problems/missing-number-lcci/description/
题目与思路分析
目标分析
- 数组
nums包含从0到n的所有整数，但其中缺了一个。编写代码找出那个缺失的数字 - 要求时间复杂度至多为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 = 0a ^ 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;}};结语
以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步
分享到此结束啦你的每一次互动，都是对作者最大的鼓励！
一键三连，好运连连！征程尚未结束，让我们在广阔的世界里继续前行！🚀
