落单的数Ⅱ
题意
给出 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。将这些单独位的二进制数再拼凑到一次。只需要进行 或运算 。
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 拼凑到一起。
代码实现
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;
}
}
原题地址
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-08-122，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录