题目描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

示例1

输入

[1,4,1,6]

返回值

[4,6]

说明

返回的结果中较小的数排在前面

思路

方法一：map

map是解这类题常用的方法，就是空间复杂度高一点。

题解：

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        map<int, bool> ans;
        int a=0, b=0;
        for(int a: array){
            if(ans[a]) ans[a] = false;
            else ans[a] = true;
        }
        for(auto it: ans){
            if(it.second) !a?a = it.first:b = it.first;
        }
        return {a,b};
    }
};

方法二：位运算

位运算是比较有趣的方法。以前遇到过只有一个数字出现一次的，所有数字异或的结果就是出现一次的数字。
现在有两个数字，则所有数字异或的结果一定是这两个数的异或。比如[1,4,1,6]的异或结果为4^6=2。
从二进制的角度来看，结果是010,那么这两个数的第一位（低位）要么同0，要么同1,第二位（低位）则一个为0，一个为1。第二位（低位）是可以标识的特殊位，它区分了这两个数。所以我们可以把所有这个位为1的异或起来，所有这个位为0的也异或起来。得到的两个数就是答案。

题解：

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        int x = 0;
        for(int c:array) x ^= c;
        int bit = 1;
        while(!(x&bit)) bit<<=1;
        int a=0, b=0;
        for(int c:array) c&bit?(a ^= c):(b ^= c);
        if(a>b) return {b, a};
        return {a, b};
    }
};

我本来想对比一下这两个程序的内存占用区别，看看位运算的方法是否能节约空间，网上大多数查看运行内存的代码是Linux和Windows的。Mac我自己用ps去获取rss对比不出来，不知道是什么原因，我最近会再查查资料，也欢迎交流。