一、题目描述

JZ40数组中只出现一次的两个数字
题目大意：一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次,请写程序找出这两个只出现一次的数字
注意审题：题目保证有两个数字只出现一次,其余数字出现两次,并且返回的结果中较小的排在前面

二、算法1（排序）

算法思路

1.总体思路：先对数组从小到大排序,这两相同的两个数就相邻了
2.采用类似双指针的思想,当下一个数和自身相同时,移动两步;当下个数与当前数不同时,则将当前数加入答案,移动一步

代码实现（C++11）

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        vector<int> ans;
        int n = array.size();
        sort(array.begin(), array.end());
        for(int i = 0; i < n; i++){
            if(i + 1 == n || array[i + 1] != array[i]){
                ans.push_back(array[i]);
                }
            else i++;
            }
        if(ans[0] > ans[1]) swap(ans[0], ans[1]);
        return ans;
    }
};

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

三、算法2（哈希表）

算法思路

1.总体思路：先用哈希表记录每个数出现的频率,然后遍历哈希表,将只出现一次的数加入答案

代码实现（C++11）

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        unordered_map<int, int> frq;
        vector<int> ans;
        for(auto & x : array) ++frq[x];
        for(auto & [key, value] : frq){
            if(value == 1) ans.push_back(key);
            }
        if(ans[0] > ans[1]) swap(ans[0], ans[1]);
        return ans;
    }
};

四、算法3（位运算）

前置知识（异或的基本性质）

算法思路

1.总体思路：有一道和它类似的题,它所指的数组中只有一个出现一次的数,而解法就是从头开始不断地异或下去,由于相同的两个数异或值为0,因此最终的异或结果就是答案
2.而本题有两个只出现一次的数a和b,我们按异或方法最终只能得到a异或b的值,就需要思考一下这两个数异或的结果有何特点
3.我们可以发现,首先这两个数一定不同,故异或结果一定不为0,那么a异或b的结果中一定有一位为1,假设是第x位,那么就说明了a和b的二进制的第x位是不同,根据这一特点,我们可以将数组分为两个集合,即第x位为1的数和第x位为0的数,两部分的异或和即为a和b的值
4.要快速求得最后一位1,可以用lowbit运算,它可以快速得到x的最后一位1

代码实现（C++11）

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        vector<int> ans;
        int n = array.size();
        int s = 0;    // a ^ b
        for(int i = 0; i < n; i++) s ^= array[i];
        int mask = lowbit(s);
        int a = 0, b;
        for(int i = 0; i < n; i++){
            if(mask & array[i]) a ^= array[i];
            }
        b = s ^ a;
        ans.push_back(a);
        ans.push_back(b);
        if(ans[0] > ans[1]) swap(ans[0], ans[1]);
        return ans;
    }

    int lowbit(int x){
        return x & -x;
    }
};

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