题目描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。

找出只出现一次的那两个元素。

样例

输入：[1,2,1,3,2,5]
输出：[3,5]

说明

• 结果输出的顺序并不重要，对于上面的例子，[5, 3] 也是正确答案。
• 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

算法

(位运算) $O(n)$

1. 根据 Single Number 的做法，此题仍然是利用异或操作。
2. 首先将所有数字进行异或，求出异或和 sum。sum 必定不为 0。
3. 找到 sum 二进制表示下不为 0 的其中一个位置。此时，我们可以根据这个位置是否为 1，将数组中的数字分为两部分。注意到，这两个数字会分别位于一部分中。
4. 将这一位为 0 的数字分为一组，为 1 的数字分为一组，分别求异或和，得到最终的两个数字。

时间复杂度

• 仅遍历两次数组，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
            sum ^= nums[i];

        int pos = 0;
        for (int i = 0; i < 32; i++)
            if ((sum >> i) & 1) {
                pos = i;
                break;
            }

        int s1 = 0, s2 = 0;
        for (int i = 0; i < nums.size(); i++)
            if ((nums[i] >> pos) & 1)
                s1 ^= nums[i];
            else
                s2 ^= nums[i];

        return vector<int>{s1, s2};
    }
};