C++ solution using unordered_set


  • 2
    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;
    }

  • 0
    W

    the complicty is o(n)?


  • 0

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


  • 0
    5

    @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).


  • 0

    @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. .


Log in to reply
 

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