C++ solution using unordered_set

• ``````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 = *it-1; 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;
}``````

• the complicty is o(n)?

• @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 (say `k`), the resulted time complexity should be something like `O(n * log_k(n))`, as the average case for a hashset operation is `O(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. .

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