落单的数Ⅲ

题意

给出2*n + 2个的数字,除其中两个数字之外其他每个数字均出现两次,找到这两个数字。

样例

给出 [1,2,2,3,4,4,5,3],返回 1 和 5

思路

这道题用到了很多位运算的小技巧。

首先将数组中所有的数进行异或,最终的结果就是两个落单的数的异或值。

根据异或的规律:两值相同则为 0,不同则为 1。两者又是两个不同的数,所以最后异或的结果肯定不为 0.

然后取出异或值的二进制位中最低一个值为 1 的数。例如对于异或值:60(111100),取最低一个值为 1 的数,也就是:4 (100)。

然后将数组所有数与这个数进行与运算,将结果为 0 的数分为一组,非 0 的数分为另一组。由于上方异或得到的规律可得,两个落单的数,肯定在两个不同的组里。

在对这两组进行 落单的数 中的操作即可分别得到两个落单的数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
/**
* @param A : An integer array
* @return : Two integers
*/
public List<Integer> singleNumberIII(int[] A) {
int xor = 0;

// xor 代表的是落单的两个数的异或值
for (int i = 0; i < A.length; i++) {
xor ^= A[i];
}

//lastBit 代表的是 xor 的二进制位中最低一个值为 1 的数。
int lastBit = xor - (xor & (xor - 1));
int r1 = 0, r2 = 0;

for (int i = 0 ; i < A.length; i++) {
if ((lastBit & A[i]) == 0) {
r1 ^= A[i];
} else {
r2 ^= A[i];
}
}
List<Integer> list = new ArrayList<Integer>();
list.add(r1);
list.add(r2);
return list;
}
}

原题地址

LintCode:落单的数Ⅲ