给出2*n + 2个的数字,除其中两个数字之外其他每个数字均出现两次,找到这两个数字。
给出 [1,2,2,3,4,4,5,3]
,返回 1 和 5
这道题用到了很多位运算的小技巧。
首先将数组中所有的数进行异或,最终的结果就是两个落单的数的异或值。
根据异或的规律:两值相同则为 0,不同则为 1。两者又是两个不同的数,所以最后异或的结果肯定不为 0.
然后取出异或值的二进制位中最低一个值为 1 的数。例如对于异或值:60(111100),取最低一个值为 1 的数,也就是:4 (100)。
然后将数组所有数与这个数进行与运算,将结果为 0 的数分为一组,非 0 的数分为另一组。由于上方异或得到的规律可得,两个落单的数,肯定在两个不同的组里。
在对这两组进行 落单的数 中的操作即可分别得到两个落单的数。
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;
}
}