给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意:
结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?
类似题目 LeetCode 137. 只出现一次的数字 II(位运算) LeetCode 136. 只出现一次的数字(异或^)
关于第二步的举例:8,13 1000 1101 ^ 0101 bit bit & -bit 0001
假如 bit = 1100 bit & -bit = 0100(得到的是最低位的1)
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int bit = 0, i, n1 = 0, n2 = 0;
for(i = 0; i < nums.size(); ++i)
bit ^= nums[i];
bit &= (-bit);
for(i = 0; i < nums.size(); ++i)
{
if((bit & nums[i]) == 0)//内层括号!!!不能少
n1 ^= nums[i];
else
n2 ^= nums[i];
}
return {n1, n2};
}
};