leetcode-128-Longest-Consecutive-Sequence

发表于   |  

TOREVIEW

描述

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

You must write an algorithm that runs in O(n) time.

Example 1:

1
2
3
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

1
2
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

分析

并查集的应用，分别判断 nums[i]+1, nums[i]-1 是否在集合中，并与 num[i] 归为一类。

解决方案1(Python)

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
34
class UnionFind:
    def __init__(self):
        self.union_find = {}
        
    def find(self, x):
        if x == self.union_find[x]:
            return x
        self.union_find[x] = self.find(self.union_find[x]);
        return self.union_find[x];
    
    def merge(self, x, y):
        self.union_find[self.find(x)] = self.find(y);

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        union_find = UnionFind()
        union_find.union_find = {i:i for i in range(len(nums))}
        value_index_map = {}
        
        for i in range(len(nums)):
            if nums[i] in value_index_map.keys():
                continue
            value_index_map.update({nums[i]: i})
            if nums[i]+1 in value_index_map.keys():
                union_find.merge(i, value_index_map[nums[i]+1])
            if nums[i]-1 in value_index_map.keys():
                union_find.merge(i, value_index_map[nums[i]-1])
        
        result = 0
        count = [0 for i in range(len(nums))]
        for i in range(len(nums)):
            count[union_find.find(i)] += 1
            result = max(count[union_find.find(i)], result)
        return result

相关问题

题目来源