Single Number II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/single-number-ii/

题目：
Given an array of integers, every element appears three times except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
a xor a = 0
a xor 0 = a
0 xor a = a
a xor b = c => a xor c = b => b xor c => a
不进位加法
Solution: Count the number of each bit.

代码：

 class Solution {  
 public:  
   // 3n + 1问题，可以理解为3进制问题  
   int singleNumber(int A[], int n) {  
     int result = 0;  
     for (int i = 0; i < 32; ++i) {  
       int count = 0;  
       int bit = 1 << i;  
       for (int j = 0; j < n; ++j) {  
         if (A[j] & bit) {  
           count++;                    
         }  
       }  
       if (count % 3 != 0) { // count % 3 == 1  
         result |= bit;  
       }  
     }  
     return result;  
   }  
 };  

扩展：
// Given an array of integers, every element appears twice except for two. Find the two singles.

代码：

 vector<int> singleNumber(int A[], int n) {  
   vector<int> num(2, 0);  
   int twoNums = 0; // compute two numbers xor  
   for (int i = 1; i < n; ++i) {  
     twoNums ^= A[i];  
   }  
   int bit = 0; // find which bit is different from lowest bit  
   for (int i = 0; i < 32; ++i) {  
     bit = 1 << i;  
     if (twoNums & bit) break;  
   }  
   // find two integers  
   for (int i = 0; i < n; ++i) {  
     if (A[i] & bit) {  
       num[0] ^= A[i];  
     } else {  
       num[1] ^= A[i];  
     }  
   }  
   if (num[0] > num[1]) swap(num[0], num[1]);  
   return num;  
 }