Single Number II
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2] Output: 3
Example 2:
Input: [0,1,0,1,0,1,99] Output: 99
class Solution {
public:
int singleNumber(vector<int>& nums)
{
// unordered_map<int,int> mp;
// int ans=0;
// for(auto p:nums)
// {
// mp[p]++;
// }
// for(auto p:mp)
// if(p.second==1)
// {
// ans=p.first;
// break;
// }
// return ans;
int low_bits = 0, hi_bits = 0;
for ( const auto &e: nums ) {
low_bits = ~hi_bits & ( low_bits ^ e );
hi_bits = ~low_bits & ( hi_bits ^ e );
}
return low_bits;
}
};
/*
App 1:
pass 1:
Use hash map key=num, val=cnt
pass 2:
Go thru the hash map and report the number whose val==1
Time = O(n), Space = O(n)
App 2:
use two hash map, seenOnce, seenTwice
1. An ele appear 1 time, put in seenOnce
2. An ele appear 2 times, put in seenTwice, remove from seenOnce
3. An ele appear 3 times, remove from seenTwice
4. Now ele in seenOnce is the result.
Time = O(n), space=O(n)
App 3:
Optimize from App 2
Using truth table
-----------------
We see that states are 1, 2, 0
seen once -> seen twice -> seen none
So we see transition is as follows. (or define state )
00 -> 01 -> 10 -> 11
h=high, l=low, i=input
h l i h' l'
0 0 0 0 0 // no input, no change
0 1 0 0 1 // no input, no change
1 0 0 1 0 // no input, no change
0 0 1 0 1 // 00->01
0 1 1 1 0 // 01->10
1 0 1 0 0 // 10->00
h' = ( h & ~l & ~i ) | ( ~h &l & i )
l' = ( ~h & l & ~i ) | ( ~h &~l & i )
= ~h & (( l & ~i ) | ( ~l & i ))
= ~h & ( l ^ i ) --> (1)
Now if l' is compulted 1st // 3rd and 5th row
h' = h & ~i & ~l' | ~h & i & ~l'
= ~l' & ( ( h & ~i ) | (~h & i) )
= ~l' & ( h ^ i)
*/
#ifdef _APP1_
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_set<int> seenOnce, seenTwice;
for ( const auto &e: nums ) {
if ( seenTwice.count (e) ) seenTwice.erase (e); // 3rd time
else if ( seenOnce.count (e) ) { // 2nd time
seenTwice.insert (e);
seenOnce.erase (e);
} else seenOnce.insert (e); // 1st time
}
auto it = seenOnce.begin();
return ( *it );
}
};
#endif
class Solution {
public:
int singleNumber(vector<int>& nums) {
int low_bits = 0, hi_bits = 0;
for ( const auto &e: nums ) {
low_bits = ~hi_bits & ( low_bits ^ e );
hi_bits = ~low_bits & ( hi_bits ^ e );
}
return low_bits;
}
};
