leetcode260.只出现一次的数字III

题目链接

260. 只出现一次的数字 III – 力扣（LeetCode）

题目理解

        不难理解，比如[1,2,1,3,2,5]中，3和5只出现过一次，因此输出3和5。主要难点在解题思路，这里不过多解释。

解题思路

        这道题和平时见到的只出现一次的数字不同。因为这次我们有两个数字之出现了一次。因此我们不能将数字转换成二进制后取模。下面我们看一下这道题怎么解：

step1.全部异或

1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
= (1^1) ^ (2^2) ^ (3^5) // 成对的互相抵消了！
= 0 ^ 0 ^ (3^5)
= 3 ^ 5
= 6

这里的6是3和5异或的结果。

把 3 和 5 写成二进制：

• 3 → 011

• 5 → 101

它们异或得到 6 → 110

关键观察：6 的二进制 110 中，第二位的 1 表示 3 和 5 在这个位置不同！(其实第三位的1也表示3和5在那一位上不同，但我们通常取最低位的1)

• 3 的第二位是 1

• 5 的第二位是 0

异或不会计算的同学去复习一下，这里不多赘述了。

step2.找异或结果最低位的1

        mix & (-mix) 能获取一个数字二进制表示中最低位的 1

        -x 操作的实际含义：

int x = 6; // 计算机中存储：0000 0110（补码）

// 当你写 -x 时，计算机做的事情：
int y = -x; // 计算过程：
// 1. 取x的补码：0000 0110
// 2. 按位取反：1111 1001
// 3. 加1：1111 1010
// 结果：这就是-6的补码表示！

        因此 mix & (-mix) 即为0000 0010，这正是 6 的最低位的 1。

step3.分家法

用第二位作为"分家标准"：

• 第二位是 1 的站左边

• 第二位是 0 的站右边

检查每个数字：

结果：

• 左边组：2, 2, 3

• 右边组：1, 1, 5

分组后我们发现：

• 3 和 5 被分到了不同的组！

• 每组的其他数字都是成对的

step4. 各组异或

左边组：2 ^ 2 ^ 3 = 3

• 2 和 2 互相抵消

• 剩下 3 ✓

右边组：1 ^ 1 ^ 5 = 5

• 1 和 1 互相抵消

• 剩下 5 ✓

以下是该例子的可视化流程：

原始数组：[1, 2, 1, 3, 2, 5]
↓
全部异或：6（3^5的混合体）
↓
找最低位1：2（二进制010）
↓
分组：
左边（第二位=1）：[2, 3, 2] → 异或得到 3
右边（第二位=0）：[1, 1, 5] → 异或得到 5
↓
答案：[3, 5]

         总结一下：先把所有数字异或得到"混合体"，找到两个单身狗不同的一个二进制位，按这个位分组，然后每组分别异或，就得到了两个数字！

详解代码

class Solution {
public:
vector<int> singleNumber(vector<int>& nums)
{
long long step1=0;
//step1.全部异或
for(auto it:nums)
{
step1^=it;
}
//step2 找异或结果最低位的1
long long step2=step1&(-step1);
//step3 分家法
int result1=0,result2=0;
//step4 各组异或
for(auto it:nums)
{
if((step2&it)!=0)
{
result1^=it;
}
else
{
result2^=it;
}
}
return {result1,result2};
}
};

        学会了就给博主点个赞呗？(✪ω✪)

———（如有问题，欢迎评论区提问）———