int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int len = 0, p, count;
while( !s.empty() ) {
auto it = s.begin();
count = 1;
for( p = *it1; s.count(p) && s.erase(p); p ) count++;
for( p = *it+1; s.count(p) && s.erase(p); p++ ) count++;
len = max( len, count );
s.erase(it);
}
return len;
}
C++ solution using unordered_set


@wxfang_4010 You have n elements in the set and you visit each element one time. That's O(n) for sure.

@Tiejun That's not true. The calculation of time complexity should take the operation cost (retrieval, insertion and removal) of the
unordered_set
as well into account. Most of the time, it behaves like constant time (when used with proper hash function). But if the number of elements (n
) is a lot more than the number of buckets (sayk
), the resulted time complexity should be something likeO(n * log_k(n))
, as the average case for a hashset operation isO(log_k(n))
(the average number of elements in each bucket).

@560889223 Just like qsort, we always regard it as an O(nlgn) algorithm, but we know it has n^2 running time in the worse case and that scenario is extremely rare in the real world. .