128. Longest Consecutive Sequence

hashtable版本 O(n)

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(begin(nums), end(nums)); // 把所有数放到hashtable里
        int res = 0;
        for (int x : nums) {
            if (s.empty()) break;
            if (s.count(x - 1)) continue;
            int len = 0;
            while (s.count(x)) { // 从nums[i]开始找递增连续数列
                s.erase(x); // 每找到一个数就删除
                ++len;
                ++x;
            }
            res = max(res, len);
        }
        return res;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end()); // 把所有数放到hashtable里
        int n = nums.size();
        int res = 0;
        for (int i = 0; i < n && !s.empty(); ++i) {
            int curr = nums[i];
            int len = 0;
            while (s.count(curr)) { // 从nums[i]开始找递增连续数列
                s.erase(curr);
                ++len;
                ++curr;
            }
            curr = nums[i] - 1; // 从nums[i] - 1开始找递减连续数列
            while (s.count(curr)) {
                s.erase(curr);
                ++len;
                --curr;
            }
            res = max(res, len);
        }
        return res;
    }
};

union-find O(n)

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        UF uf;
        for (int n : nums) {
            if (uf.has(n)) continue;
            uf.add(n);
            if (uf.has(n - 1)) {
                uf.merge(n - 1, n);
            }
            if (uf.has(n + 1)) {
                uf.merge(n + 1, n);
            }
        }
        return uf.mx;
    }

    struct UF {
        void add(int x) {
            parent[x] = x;
            size[x] = 1;
            mx = max(mx, 1);
        }

        bool has(int x) {
            return parent.find(x) != parent.end();
        }

        int getParent(int x) {
            while (parent[x] != parent[parent[x]]) {
                x = parent[x] = parent[parent[x]];
            }
            return parent[x];
        }

        void merge(int x, int y) {
            int px = getParent(x);
            int py = getParent(y);
            if (px != py) {
                parent[px] = py;
                int sz = size[px] + size[py];
                size[px] = size[py] = sz;
                mx = max(mx, sz);
            }
        }

        unordered_map<int, int> parent, size;
        int mx = 0;
    };
};