Posted on 2014-01-16 03:25
Uriel 閱讀(325)
評論(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 };