#83 Single Number II

题目描述：

Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.

Have you met this question in a real interview?  Yes Example

Given [1,1,2,3,3,3,2,2,4,1] return 4

Challenge 

One-pass, constant extra space.

题目思路：

这题我感觉很无聊，就放弃了挑战constant extra space（因为看reference code感觉还是一个bit manipulate的trick）。建一个map存遇到的数和出现的次数，当发现一个数出现了3次以后，就把这个数从map中删去。这样遍历完A以后，最后得到的map就只有一个数，就是那只单身狗。

Mycode（AC = 205ms）：

class Solution { public: /** * @param A : An integer array * @return : An integer */ int singleNumberII(vector<int> &A) { // write your code here map<int,int> helper; for (int i = 0; i < A.size(); i++) { if (helper.find(A[i]) != helper.end()) { if (helper[A[i]] == 2) helper.erase(helper.find(A[i])); else helper[A[i]]++; } else { helper[A[i]] = 1; } } return helper.begin()->first; } };