Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
#define STOP system("pause")
#if 0
class Solution {
public:
	int singleNumber(int A[], int n) {
		unordered_map<int ,int> hash_map;
		for (int i = 0; i < n; i++){
			++hash_map[A[i]];
			if (hash_map[A[i]] == 3) hash_map.erase(A[i]);
		}
		return hash_map.begin()->first;
	}
};
#elif 1
class Solution {
public :
	int singleNumber(int A[], int n){
		vector<int> bit_num(32, 0);
		for (int i = 0; i < n; i++){
			for (int j = 0; j < 32; j++){
				if (A[i] & 1 << j)
					bit_num[j]++;
			}
		}
		int res = 0;
		for (int i = 0; i < 32; i++)
			res += (bit_num[i] % 3) << i;
		return res;
	}
};
#endif 
void test0(){
	int A[] = { 1, 2, 3, 1, 2, 3, 1, 2, 3, 6 };
	Solution ss;
	int res = ss.singleNumber(A,10);
	if (res != 6)
		printf("error");
	else
		printf("passed");
}
int main(){
	test0();
	STOP;
	return 0;
}

Single Number II

原文：http://blog.csdn.net/u011409995/article/details/39009059