My simple answer in Python. Real O(n).


  • 3
    M
    class Solution(object):
        def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            dictionary = {}
            maxLength = 1
            for n in nums:
                length = 1
                left = 0
                right = 0
                if n in dictionary:
                    continue
                dictionary[n] = 1
                if n - 1 in dictionary:
                    length += dictionary[n - 1]
                    left = dictionary[n - 1]
                if n + 1 in dictionary:
                    length += dictionary[n + 1]
                    right = dictionary[n + 1]
                dictionary[n - left] = length
                dictionary[n + right] = length
                if maxLength < length:
                    maxLength = length
            return maxLength

  • 0
    X

    Cannot understand. Can you write some comments? thanks!


  • 0

    Maybe i cann't describle it correctly and resonably

    dictionary = {} dictionary[x] = y means : the length 'y' of the longest consecutive sequence which contains the current element 'x'.
    every time in the for circle, we find an element which has not been visited . Then we calculate and update the maxlenth the element can constructe.


  • 0
    W

    why the complicity is O(n)?
    i in dict is O(n)
    O(n^2) to the whole process


  • 0
    M

    @weiheng4
    It's the complexity of a single dict lookup, which is on average O(1) and at worst O(n). .list() will always be O(n). wiki.python.org/moin/TimeComplexity


Log in to reply
 

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