βSingle Number II
Using Map
int Solution::singleNumber(const vector<int> &A) {
map<int, int> freq;
for(int x: A)
freq[x]++;
for(auto p: freq)
if(p.second == 1)
return p.first;
return -1;
}
Time Complexity: β
Space Complexity: β
Using Sorting
int Solution::singleNumber(const vector<int> &A) {
vector<int> B(A.begin(), A.end());
sort(B.begin(), B.end());
int i = 0;
while(i + 1 < A.size()) {
if(B[i] != B[i + 1])
return B[i];
i = i + 3;
}
if(A.size() == 1)
return B.front();
else
return B.back();
}
Time Complexity: β
Space Complexity: for duplicating array for sorting
Counting Set Bits
int Solution::singleNumber(const vector<int> &A) {
int res = 1;
for(int shift = 0; shift < 32; shift++) {
int count = 0;
for(const int &x: A)
count += x & (1<<shift);
if(count % 3)
res = res | (1 << shift);
}
}
Last updated