个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创位运算(7)_消失的两个数字
目录
温馨提示:
1. 题目链接 :
2. 题目描述 :
3. 解法(位运算) :
算法思路 :
代码展示 :
结果分析 :
温馨提示:
本文的算法题需要一些位运算知识的基础,如果大家还不是很了解的话,可以先去看下面的博客:
位运算(1)_常见位运算总结-CSDN博客
而且本题就是leetcode上268.丢失的数字 + 260.只出现一次的数组III组合起来的题.这两道题我也出过相关博客,大家想看的可以自行去下面博客查看:
位运算(4)_丢失的数字-CSDN博客
位运算(2)_5道算法题入门位运算-CSDN博客
1. 题目链接 :
OJ链接 : 消失的两个数字
2. 题目描述 :
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1] 输出: [2,3]
示例 2:
输入: [2,3] 输出: [1,4]
提示：
nums.length <= 30000
3. 解法(位运算) :
算法思路 :
1. 使用异或运算 :
异或运算的性质是：相同的数字异或结果为 0，任何数字与 0 异或结果为该数字本身。
通过对数组中的所有数字以及从 1 到 n + 2 的所有数字进行异或操作，可以得出一个结果 ret，它是缺失的两个数字 a 和 b 的异或值：ret = a ^ b。
2. 确定分组依据 :由于 a 和 b 是不同的数字，ret 的二进制表示中至少有一位是 1。我们需要找到这一位，以便将数字分为两组。
通过逐位检查 ret，找到从右侧开始第一个为 1 的位，这个位的索引记为 count。
3. 分组和再次异或 :根据 count 位的值（0 或 1）将从 1 到 n + 2 的数字和数组中的数字分为两组：一组是 count 位为 1 的数字，另一组是 count 位为 0 的数字。
对每组中的数字进行异或操作，分别得到两个缺失的数字 a 和 b。
4. 返回结果 :最后将两个缺失的数字以数组形式返回。
代码展示 :
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int ret = 0;
for(auto ch : nums)
ret ^= ch;
for(int i = 1; i <= nums.size() + 2; i++)
ret ^= i;
int count = 0;
while(1)
{
if(((ret >> count) & 1) == 1) break;
count++;
}
int a = 0, b = 0;
for(int i = 1; i <= nums.size() + 2; i++)
{
if(((i >> count) & 1) == 1) a ^= i;
else b ^= i;
}
for(auto ch : nums)
{
if(((ch >> count) & 1) == 1) a ^= ch;
else b ^= ch;
}
return {a, b};
}
};
结果分析 :
时间复杂度 :
遍历数组和 1 到 n + 2 的数字各一次，因此总体时间复杂度是 O(n)，其中 n 是数组的长度。
空间复杂度 :仅使用了常量空间来存储几个整数，空间复杂度为 O(1)。
总结 :
该算法利用了异或运算的特性，通过将数字分组并分别异或，成功找出了缺失的两个数字。这种方法不仅高效，而且由于只需要常量空间，避免了使用额外的数据结构，适合解决类似的缺失数字问题。
