题目链接：剑指 Offer 56 - I. 数组中数字出现的次数
方法：位运算 + 分类
解题思路
异或运算：当两个相同的数异或时，结果为\(0\)；
对于本题，假设答案为\(res1\) 和 \(res2\)，那么对数组中所有的数求异或时，其结果实际等于 \(res1\) ^ \(res2\)；并且此结果中二进制位为1的位置就是\(res1\) 和 \(res2\)对应的二进制位中不同位置，说明\(res1\) 和 \(res2\)在该位的二进制位一个是\(0\)一个是\(1\)。那么我们可以根据其中某个不同的位作为基准，将该位为\(0\)的分为一类，为\(1\)的分为一类，对每一类求异或，就得到了两个答案。为了方便计算选取\(res1\) ^ \(res2\)结果中的最后一位\(1\)的位置为基准。
代码
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int x = 0;
for (auto &num : nums) x ^= num; // 计算 res1 ^ res2
int idx = 0;
while (!(x & 1)) { // 找到最后一位1的位置（从右到左）
x >>= 1;
idx ++ ;
}
int res1 = 0, res2 = 0;
for (auto &num : nums) { // 分类求异或
if ((num >> idx) & 1) res1 ^= num;
else res2 ^= num;
}
return {res1, res2};
}
};
复杂度分析
时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。