题目描述
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
示例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对比不出来，不知道是什么原因，我最近会再查查资料，也欢迎交流。
