描述

这是一篇针对初学者的题解，共用两种方法解决。
知识点：数组，位运算，哈希
难度：一星

题解

题目抽象：给定一个数组，数组中只有2个数字出现了一次，其余都出现了2次，找出这2个数字。

方法一：哈希法

很显然的方法，遍历一遍数组，用map记录出现的次数，然后再遍历一遍数组，找出出现1次的数字。

代码

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        unordered_map<int, int> mp;
        for (const int k : data) ++mp[k];
        vector<int> ret;
        for (const int k : data) {
            if (mp[k] == 1) {
                ret.push_back(k);
            } 
        }
        *num1 = ret[0];
        *num2 = ret[1];
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

方法二：位运算

前提知识：
异或运算：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。

• n^0 = n;
• n^n = 0;
• n^n^m = n^(n^m) 满***换律

所以，我们可以让数组中的每一个数异或一下，最后会得到一个结果ret，就是两个出现一次的数字的异或结果这个结果肯定是由两个不同数字异或而来，因此我们找ret二进制中为1的位置i，因为1一定是由0,1异或而来，因此要求得两个数中，一定有一个数的二进制中的第i个位置为1， 一个为0.

如何找到位置i？可用i = ret ^ (-ret)
因为计算机用补码存取二进制数，而负数的补码为反码+1，举个例子
假如ret = 1110 ， -ret = 0010 , 所以 i = 0010
所以，再异或一遍即可得到答案。

代码

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int ret = 0;
        for (const int k : data) ret ^= k;
        ret &= (-ret);
        *num1 = 0, *num2 = 0;
        for (const int k : data) {
            if (k & ret) *num1 ^= k;
            else *num2 ^= k;
        }
    }
};

时间复杂度：O(n)
空间复杂度：O(1)