It’s not the load that breaks you down, it’s the way you carry it.
压垮你的不是那些重担，而是你背负的方式。
问题描述
给定一个整数数组nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
位运算解决
前面刚讲过一个和这题类似的题494，位运算解只出现一次的数字，只不过第494题只有一个数字出现一次，但这题是有两个数字只出现一次。我们知道在位运算中异或运算具有交换律，也就是
A^B^C=A^C^B
我们还知道一个数字和自己异或，结果是0，也就是
A^A=0；
任何数字和0异或结果还是他自己
A^0=A；
有了上面的3个公式，这题就很容易解了，假如数组的元素是
[a，e，f，h，b，f，h，e]
我们看到这个数组中只有a和b出现了一次，其他的元素都出现了2次。如果我们把数组中的所有元素全部都异或一遍,也就是下面这样
a^e^f^h^b^f^h^e
因为异或具有交换律，我们可以把它整理成
a^b^(f^f)^(h^h)^(e^e)
结果就是a^b^0^0^0=a^b
因为a和b是不相等的，所以他俩的异或结果不可能是0，只要不为0，那么这个结果转化为二进制的时候肯定有1。关于异或运算有下面几个规律
1^1=0;
1^0=1;
0^1=1;
0^0=0;
我们看到结果为1的要么是0和1异或，要么是1和0异或。也就是说我们可以根据a和b某一位是否是0和1来把数组分为两组，并且a和b都不在同一组
举个例子，比如数组
[12，13，14，17，14，12]
那么他们异或的结果就是13^17
我们看到异或结果最右边的1，也就是红色部分，根据这个位置是0还是1把原数组分为两组，那么13和17肯定不在同一组。那么每组就变成了只有一个数字出现一次，其他数字都出现两次。然后我们就可以使用494，位运算解只出现一次的数字的方式来解了。代码如下
1public int[] singleNumber(int[] nums) { 2 int bitmask = 0; 3 //把数组中的所有元素全部都异或一遍 4 for (int num : nums) { 5 bitmask ^= num; 6 } 7 //因为异或运算的结果不一定都是2的n次幂， 8 //在二进制中可能会有多个1，为了方便计算 9 //我们只需保留其中的任何一个1，其他的都10 //让他变为0，这里保留的是最右边的111 bitmask &= -bitmask;12 int[] rets = {0, 0};13 for (int num : nums) {14 //然后再把数组分为两部分，每部分在15 //分别异或16 if ((num & bitmask) == 0) {17 rets[0] ^= num;18 } else {19 rets[1] ^= num;20 }21 }22 return rets;23}
上面的位运算bitmask &= -bitmask;表示的是把bitmask二进制中最右边的1保留，其他位置全部变为0，随便找个数据打印一下
再来看一下运算结果
总结
这题不是很难，但做这题需要对异或运算熟练掌握才行。
长按上图，识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧
本文分享自微信公众号 - 数据结构和算法（sjjghsf）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
