Single Number II
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
1 class Solution { 2 public: 3 int singleNumber(int A[], int n) { 4 5 unordered_map<int, int> singleMap; 6 for(int i = 0; i < n; i++) 7 { 8 if(singleMap.find(A[i]) != singleMap.end()) 9 singleMap[ A[i] ]++; 10 else 11 singleMap[ A[i] ] = 1; 12 } 13 14 for(unordered_map<int, int>::iterator it = singleMap.begin(); it != singleMap.end(); it++) 15 { 16 if(it->second != 3) 17 return it->first; 18 } 19 } 20 };