Posted on 2014-01-16 03:25
Uriel 閱讀(345)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
LeetCode 、
位運(yùn)算
前一題的解題報(bào)告把這題的也說(shuō)了。。一堆出現(xiàn)3次的數(shù)中找出唯一一個(gè)只出現(xiàn)了1次的，就是每位按位累加，然后mod 3，最后剩下的就是，但是WA了好多次，符號(hào)略搞。。
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 };
另一種比較高大上的做法是開(kāi)三個(gè)變量，分別標(biāo)記出現(xiàn)過(guò)一次，兩次，三次的，每處理一個(gè)數(shù)的時(shí)候分別計(jì)算異或、與、非[出現(xiàn)三次時(shí)前兩個(gè)變量都為1，取反后利用第三個(gè)變量清除該數(shù)]，然后第一個(gè)變量中剩下的就是只出現(xiàn)過(guò)一次的數(shù)
代碼巨優(yōu)美~
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 };