[剑指offer]数组中只出现一次的两个数字
程序员文章站
2022-03-08 16:23:16
...
数组中只出现一次的两个数字
题目
一个整型数组里除了两个数字之外,其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。
你可以假设这两个数字一定存在。
样例
输入:[1, 2, 3, 3, 4, 4]
输出:[1, 2]
题解
原理
- 两个相同的数字相异或后为 0
思路
- 将所给序列中的所有数进行异或运算得到结果 sum
- 随机取 sum 中第 tag 位为1的数,并记录 tag
- 将所给序列分为两个集合,第 tag 位为 1 的集合和第 tag 位不是 1 的集合
- 其中,只出现一次的两个数字 a、b 分别在这两个集合,且相同的元素是在同一个集合里面
- 于是现在只需要将两个集合分别异或即可得到 a 和 b
class Solution {
public:
vector<int> findNumsAppearOnce(vector<int>& nums) {
int sum = 0, tag = 0, a = 0, b = 0;
for (auto x : nums) sum ^= x;
while (!(sum >> tag & 1)) tag ++;
for (auto x : nums)
if ((x >> tag) & 1) a ^= x;
else b ^= x;
return {a, b};
}
};