题目链接:https://leetcode.cn/problems/single-number-iii/
思路如下:
从头到尾依次异或数组中的每一个数字,那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次,在异或中全部抵消掉了。
由于这两个数字肯定不一样,那么这个异或结果肯定不为
0
0
0,也就是说,在这个结果数字的二进制表示中至少有一位为
1
1
1。我们在结果数字中找到第一个为
1
1
1 的位的位置,记为第
k
k
k 位。
现在我们以第
k
k
k 位是不是
1
1
1 为标准把原数组中的数字分成两个子数组,第一个子数组中每个数字的第
k
k
k 位都为
1
1
1,第二个子数组的每个数字的第
k
k
k 位都为
0
0
0,这样在每个子数组中,包含一个只出现一次的数字,而其他数字都出现两次,于是将本题转化为 LeetCode 136. 只出现一次的数字。
C++ 代码如下:
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int xorsum = 0;
for (auto &x : nums) {
xorsum ^= x;
}
int lowbit = (xorsum == INT_MIN) ? xorsum : (xorsum & -xorsum);
int x1 = 0;
for (auto &x : nums) {
if (x & lowbit) {
x1 ^= x;
}
}
int x2 = xorsum ^ x1;
return {x1, x2};
}
};