128. Longest Consecutive Sequence

Medium (Trung bình) C++ Python 🔗 Xem trên LeetCode

📋 Đề Bài

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:

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:

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

 

Constraints:

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

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)Union Find (Tập hợp rời rạc)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

C++ 0128-longest-consecutive-sequence.cpp 
class DSU {
private:
    unordered_map<int, int> parent, rank;
    int maxRank;

public:
    DSU() {
        maxRank = 1;
    }

    void add(int u) {
        parent[u] = u;
        rank[u] = 1;
    }

    int find(int u) {
        if (u == parent[u]) {
            return parent[u];
        }
        return parent[u] = find(parent[u]);
    }

    void _union(int u, int v) {
        if (!parent.count(v)) {
            return;
        }

        int pu = find(u);
        int pv = find(v);

        if (pu != pv) {
            if (rank[pu] > rank[pv]) {
                parent[pv] = pu;
                rank[pu] += rank[pv];
            }
            else {
                parent[pu] = pv;
                rank[pv] += rank[pu];
            }
            maxRank = max({maxRank, rank[pu], rank[pv]});
        } 
    }

    int getMaxRank() {
        return maxRank;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        const int n = nums.size();

        if (n <= 1) {
            return n;
        }

        DSU dsu;

        unordered_set<int> us(nums.begin(), nums.end());

        for (int num : us) {
            dsu.add(num);
            dsu._union(num, num - 1);
            dsu._union(num, num + 1);
        }

        return dsu.getMaxRank();
    }
};
Python 0128-longest-consecutive-sequence.py 
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        setNums = set(nums)
        ans = 0
        
        for num in nums:
            if num - 1 not in setNums:
                step = num + 1
                while step in setNums:
                    step += 1
                ans = max(ans, step - num)
                
        return ans