LeetCode_Longest Consecutive Sequence

Posted on | In | Views:

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity.
（时间复杂度为O(n)，乱序数组中找到最长连续的数列）

Example:



1. 哈希

使用 set 对数组进行hash，这样可以实现遍历数组时迅速定位，具体实现过程如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        
        res = 0
        for i in range(len(nums)):
            if nums[i]-1 not in s:
                j = nums[i]
                while j in s:
                    j += 1
                res = max(res, j - nums[i])
        
        return res

2. 并查集

并查集是一种常用的解决联通性问题的一种数据结构。首先对数组中的每个数字建立 数->index 的映射，在映射过程中维护并查集将连续的数字的根节点合并，最终判断根节点最多的那一个也就是联通子图中的最大个数。具体实现方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def find(self, i):
        if self.parent[i] != -1:
            return self.find(self.parent[i])
        return i
    
    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        self.parent[root_i] = root_j
    
    def longestConsecutive(self, nums: List[int]) -> int:
        n = len(nums)
        self.parent = [-1 for _ in range(n)]
        
        nums_map = {}
        for i in range(n):
            if nums[i] in nums_map:
                continue
    
            nums_map[nums[i]] = i
            if nums[i]-1 in nums_map:        
                self.union(i, nums_map[nums[i]-1])
            if nums[i]+1 in nums_map:
                self.union(i, nums_map[nums[i]+1])
        
        max_length = 0
        count = [0 for i in range(n)]
        for i in range(n):
            count[self.find(i)] += 1
            max_length = max(count[self.find(i)], max_length)
        
        return max_length