题解 | #数组中只出现一次的数字#

题目主要信息:

题目给定一个整型数组，其中有两个数字只出现了1次，其余数字都出现了两次，需要找到这两个数字

具体思路:

既然要找出唯二出现次数为1的两个数字，那我们可以直接统计数组中各个数字出现的次数，然后找出次数为1的两个就可以了。

step 1：用unordered_map建立一个哈希表，用来统计数组每个元素出现的次数。
step 2：遍历数组，使用哈希表计数。
step 3：遍历哈希表，找到频率为1的两个数字录入输出数组。
step 4：将输出数组的值录入指针参数。

可以参考如下图示： alt

代码实现:

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        unordered_map<int, int> mp; //统计数组中数字出现的次数
        vector<int> res;
        for(int i = 0; i < data.size(); i++) //遍历数组
            mp[data[i]]++; //统计次数
        for(auto iter = mp.begin(); iter != mp.end(); iter++){ //遍历哈希表
            if(iter->second == 1) //找到频率为1的数字
                res.push_back(iter->first);
        }
        *num1 = res[0]; //答案录给指针
        *num2 = res[1];
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，遍历一次数组，再遍历一次哈希表
空间复杂度： $O (n)$ ，数组中不同的数字共有 $\frac{n-2}2+2$ 个，因此哈希表长度为 $O (n)$ 级