落单的数Ⅲ
题意
给出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;
}
}
原题地址
举报
腾讯云开发者
