• ``````class Solution {
public:
int longestConsecutive(vector<int> &num)
{
if(num.size() == 0) return 0;
if(num.size() == 1) return 1;
int len = 1, max = 0;
sort(num.begin(),num.end());
for(int i=0; i<num.size()-1; ++i)
{
if(num[i]+1 == num[i+1])
++len;
else if(num[i] == num[i+1])
continue;
else
{
len = 1;
if(max >= num.size()-(i+1))// If the current largest length of LCS is greater than the number of remaining ,then break.
break;
}
max = max > len ? max : len;
}
return max = max > len ? max : len;
}
};
``````

The time complexity of sort() is O(nlogn), thus this code doesn't meet the problem's need.

so ,the right code is here

``````class Solution {
public:
int longestConsecutive(vector<int> &num)
{
if(num.size() <1) return num.size();
unordered_map<int,int> a;
int len = num.size();
int result=0;
for(int i=0; i<len; ++i)
a.insert(make_pair(num[i],1));
for(int i=0; i<len; ++i)
{
if(a.find(num[i]) == a.end())
continue;
int findLeft = num[i], findRight = num[i];
int max = 1;
while(a.find(--findLeft) != a.end())
{
max += 1;
a.erase(findLeft);
}
while(a.find(++findRight) != a.end())
{
max += 1;
a.erase(findRight);
}
a.erase(num[i]);
result = result > max ? result : max;
}
return result;
}
};``````

• The time complexity of sort() is O(nlogn), thus this code doesn't meet the problem's need.

• this is right , I have fixed it.

• You new code is still not O(N) but O(NlogN)

• i don't know why ? please explain it . thanks.

• the complexity of insert operation in std::map is O(log n)

• why the insertion of map is O(lg n) instead of O(1)?

• isn't the code inside the two while loop called more than once?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.