leetcode-128-Longest Consecutive Sequence

Posted on | In , | |
Words count in article: 405 | Reading time ≈ 2

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

Your algorithm should run in O(n) complexity.

1
2
3
4
5
Example:

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

暴力？排序？哈希？

Approach 1: Brute Force

Time complexity : O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestConsecutive(self, nums):
        longest_streak = 0

        for num in nums:
            current_num = num
            current_streak = 1

            while current_num + 1 in nums:
                current_num += 1
                current_streak += 1

            longest_streak = max(longest_streak, current_streak)

        return longest_streak

Approach 2: Sorting

If we can iterate over the numbers in ascending order, then it will be easy to find sequences of consecutive numbers. To do so, we can sort the array.

Time complexity : O(nlgn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestConsecutive(self, nums):
        if not nums:
            return 0

        nums.sort()

        longest_streak = 1
        current_streak = 1

        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                if nums[i] == nums[i-1]+1:
                    current_streak += 1
                else:
                    longest_streak = max(longest_streak, current_streak)
                    current_streak = 1

        return max(longest_streak, current_streak)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty())
            return 0;
        sort(nums.begin(), nums.end());
        int global = 1;
        int local = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1] + 1) {
                local++;
            } else if (nums[i] != nums[i - 1]) {
                local = 1;
            }
            global = max(global, local);
        }
        return global;
    }
};

Approach 3: HashSet and Intelligent Sequence Building

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestConsecutive(self, nums):
        longest_streak = 0
        num_set = set(nums)

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak
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
35
36
37
38
39
40
41
class Solution {
public:
    int longestConsecutive(vector<int>& nums) 
    {
        if(nums.empty()) return 0;
        
        std::unordered_set<int> numSet;
        for(int n : nums) numSet.insert(n);
        
        int res = 1;
        for(int n : nums)
        {
            auto it = numSet.find(n);
            if(it == numSet.end()) continue;
            numSet.erase(it);
            
            int rightMost = n+1;
            while(true)
            {
                auto it = numSet.find(rightMost);
                if(it == numSet.end()) break;
                numSet.erase(it);
                rightMost++;
            }
            
            int leftMost = n-1;
            while(true)
            {
                auto it = numSet.find(leftMost);
                if(it == numSet.end()) break;
                numSet.erase(it);
                leftMost--;
            }
            
            int tmp = rightMost - leftMost - 1;
            if(tmp > res) res = tmp;
        }
        
        return res;
    }
};
Donate? comment?