499，位运算解只出现一次的数字 III

Original 山大王wld 数据结构和算法 2022-06-18

收录于合集 #算法图文分析 162个

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，这里保留的是最右边的1
11    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}