落单的数Ⅱ

题意

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

样例

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

思路

这道题跟 落单的数 很类似,只不过这里就不能简单的使用异或运算来得出结果了。

可以记录 32 位二进制中 1 出现的个数,当个数达到 3,则将个数归零。最终剩下的就是落单的数。

如一个数组 [2, 2, 2, 3] :

2 的二进制是 0000 0000 0000 0000 0000 0000 0000 0010
3 的二进制是 0000 0000 0000 0000 0000 0000 0000 0011

将数组中所有元素的二进制位 1 的数量加在一起就是 0000 0000 0000 0000 0000 0000 0000 0041

当个数达到3,则将个数归零,最终结果就是 0000 0000 0000 0000 0000 0000 0000 0011

在实际计算中每次是取一位,也就是第一次取到的是 1,第二次取到的是 4,4 满 3 对三取模即可(4 % 3),所以第二次取到的数应该算为 1。将这些单独位的二进制数再拼凑到一次。只需要进行 或运算

1
2
3
4
  0000 0000 0000 0000 0000 0000 0000 0001
| 0000 0000 0000 0000 0000 0000 0000 0010
-----------------------------------------
0000 0000 0000 0000 0000 0000 0000 0011

如此即可将每一位的 1 拼凑到一起。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
/**
* @param A : An integer array
* @return : An integer
*/
public int singleNumberII(int[] A) {
int count = 0;
int result = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < A.length; j++) {
count += A[j] >> i & 1;
count %= 3;
}
result |= count << i;
count = 0;
}
return result;
}
}

原题地址

LintCode:落单的数Ⅱ