Has any one an idea how to solve this problem without using HashMap? I don't think that when using map.find() or map.contains() inside for-next solution complexity still remains O(n).
Please, correct me if i'm wrong.
i use radix sort to do O(n). although it takes more memory than solution using hashmap, it also use O(n) memory.
class Solution {
public:
int longestConsecutive(vector<int> &num) {
vector<int> radix[11][19];
for (int it = 0; it < num.size(); ++it) {
radix[0][num[it]%10+9].push_back(num[it]);
}
int pow10 = 1;
for (int i = 1; i < 11; ++i) {
pow10 *= 10;
for (int j = 0; j < 19; ++j) {
for (vector<int>::iterator it = radix[i-1][j].begin(); it != radix[i-1][j].end(); ++it) {
radix[i][((*it)/pow10)%10+9].push_back(*it);
}
}
}
vector<int> ans;
for (int j = 0; j < 19; ++j) {
for (vector<int>::iterator it = radix[10][j].begin(); it != radix[10][j].end(); ++it) {
ans.push_back(*it);
}
}
int cons = 0, longest = 0;;
int prev = 0;
for (int it = 0; it < ans.size(); ++it) {
printf("%d ", ans[it]);
if (cons) {
if (ans[it-1]+1 == ans[it]) {
cons++;
prev = ans[it];
}
else if (ans[it-1] != ans[it]) {
cons = 0;
}
}
if (cons == 0) {
cons = 1;
prev = ans[it];
}
longest = max(longest, cons);
}
longest = max(longest, cons);
return longest;
}
};