Accepted 24ms c++ solution use std::set, easy understand.


  • 0
    class Solution {
    public:
        int longestConsecutive(std::vector<int> &num) {
    		if (num.size() < 2)
    			return num.size();
    		std::set<int> nums;
            for (int i = 0; i != num.size(); ++i)
    			nums.insert(num[i]);
    		std::set<int>::const_iterator it = nums.begin();
    		int length = 1, start = *it, max_length = length;
            for (++it; it != nums.end(); ++it)
    			if (*it != start + length) {
    				max_length = std::max(max_length, length);
    				length = 1;
    				start = *it;
    			}
    			else
    				++length;
    		return std::max(max_length, length);
        }
    };

  • 0
    D

    The set.insert() operation takes log(n) since a set is typically implemented as a tree. The overall time complexity of this implementation is O(n log(n)).


  • 0
    G

    I think your solution needs sorting first, or the result may be unreliable. And the sorting process is O(n log(n)) .


Log in to reply
 

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