欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[剑指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};
    }
};