卖萌的弱渣

I am stupid, I am hungry.

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example:

Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Solution

  • hash_map:{nums[i]:False}
  • 使用一个哈希表，在Python中是字典dict数据类型。dict中的映射关系是{x in num：False}，这个表示num中的x元素没有被访问过，如果被访问过，则为True。如果x没有被访问过，检查x+1，x+2…，x-1，x-2是否在dict中，如果在dict中，就可以计数。最后可以求得最大长度。
(Longest-Consecutive-Sequence.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hash_map = {x: False for x in nums}

        for i in hash_map:
            if hash_map[i] == False:
                # find up
                up = i
                while up in hash_map:
                    hash_map[up] = True
                    up +=1
                # find down
                down = i-1
                while down in hash_map:
                    hash_map[down] = True
                    down -= 1

                if (up-down-1>max):
                    max = up-down-1
        return max