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

题目主要信息:

• 题目给定一个整型数组，其中有两个数字只出现了1次，其余数字都出现了两次，需要找到这两个数字
• 输出按照非降序排列

具体思路:

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

• step 1：用unordered_map建立一个哈希表，用来统计数组每个元素出现的次数。
• step 2：遍历数组，使用哈希表计数。
• step 3：遍历哈希表，找到频率为1的两个数字录入输出数组。
• step 4：比较输出数组两个元素大小，交换次序做到降序输出。

可以参考如下图示：

代码实现:

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        unordered_map<int, int> mp; //统计数组中数字出现的次数
        vector<int> res;
        for(int i = 0; i < array.size(); i++) //遍历数组
            mp[array[i]]++; //统计次数
        for(auto iter = mp.begin(); iter != mp.end(); iter++){ //遍历哈希表
            if(iter->second == 1) //找到频率为1的数字
                res.push_back(iter->first);
        }
        if(res[0] > res[1]) //比较大小，非降序排序
            swap(res[0], res[1]);
        return res;
    }
};

复杂度分析：

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