Posted on 2014-01-16 03:25
Uriel 阅读(307)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode 、
位运算
前一题的解题报告把这题的也说了。。一堆出现3次的数中找出唯一一个只出现了1次的，就是每位按位累加，然后mod 3，最后剩下的就是，但是WA了好多次，符号略搞。。
1 class Solution {
2 public:
3 int singleNumber(int A[], int n) {
4 unsigned int res = 0;
5 for(int j = 0; j < 32; ++j) {
6 int tp = 0;
7 const unsigned int pos = 1 << j;
8 for(int i = 0; i < n; ++i) {
9 tp += (A[i] & pos) > 0;
10 }
11 res |= (!(tp % 3)) ? 0 : pos;
12 }
13 return (int)res;
14 }
15 };
另一种比较高大上的做法是开三个变量，分别标记出现过一次，两次，三次的，每处理一个数的时候分别计算异或、与、非[出现三次时前两个变量都为1，取反后利用第三个变量清除该数]，然后第一个变量中剩下的就是只出现过一次的数
代码巨优美~
1 class Solution {
2 public:
3 int singleNumber(int A[], int n) {
4 int tp3, tp1 = 0, tp2 = 0;
5 for(int i = 0; i < n; ++i) {
6 tp2 |= tp1 & A[i];
7 tp1 ^= A[i];
8 tp3 = ~(tp1 & tp2);
9 tp1 &= tp3;
10 tp2 &= tp3;
11 }
12 return tp1;
13 }
14 };