Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Single Number II-2014.01.16

Posted on 2014-01-16 03:25 Uriel 阅读(314) 评论(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 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理