128. Longest Consecutive Sequence

• unordered_map 29ms
• unordered_set 19ms
• sort 13ms
• union-find 35ms

unordered_map

我们也可以采用哈希表来做，刚开始哈希表为空，然后遍历所有数字，如果该数字不在哈希表中，那么我们分别看其左右两个数字是否在哈希表中，如果在，则返回其哈希表中映射值，若不在，则返回0，然后我们将left+right+1作为当前数字的映射，并更新res结果，然后更新d-left和d-right的映射值，参见代码如下：

use unordered_map to store the sequence length for current number. 29 ms

int longestConsecutive(vector<int>& nums) {
    unordered_map<int, int> m;
    int maxLength = 0;
    for (int x: nums) {

        if (m.find(x) != m.end()) continue;

        auto it = m.find(x-1);
        int left = it == m.end() ? 0: it->second;

        it = m.find(x+1);
        int right = it == m.end() ? 0 : it->second;

        int size = 1+right+left;
        m[x] = size;
        maxLength = max(maxLength, size);
        m[x+right] = size;
        m[x-left] = size;
    }
    return maxLength;

}

unordered_set

这道题要求求最长连续序列，并给定了O(n)复杂度限制，我们的思路是，使用一个集合set存入所有的数字，然后遍历数组中的每个数字，如果其在集合中存在，那么将其移除，然后分别用两个变量pre和next算出其前一个数跟后一个数，然后在集合中循环查找，如果pre在集合中，那么将pre移除集合，然后pre再自减1，直至pre不在集合之中，对next采用同样的方法，那么next-pre-1就是当前数字的最长连续序列，更新res即可。代码如下：

16ms 查询完直接erase

    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_set<int> s(nums.begin(), nums.end());
        for (int val : nums) {
            if (!s.count(val)) continue;
            s.erase(val);
            int pre = val - 1, next = val + 1;
            while (s.count(pre)) s.erase(pre--);
            while (s.count(next)) s.erase(next++);
            res = max(res, next - pre - 1);
        }
        return res;
    }

19ms

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> mySet(nums.begin(), nums.end());
    int result = 0;

    for (int i=0; i<nums.size(); i++)
    {
        //don't compare if the element is not the beginning of a sequence.
        if (mySet.find(nums[i]-1) != mySet.end()) continue;

        //we found an element that could be a beginning of a sequence, now loop thru the hash set for a sequence.
        int length = 0;
        while (mySet.find(nums[i]++) != mySet.end()) 
            length++;
        result = max(result, length);
    }
    return result;
}

sort

Time Complexity: O(nlogn +n)

int longestConsecutive(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int maxLength = 1, currentLength = 1;
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] == nums[i-1]) continue;
        if (nums[i] == nums[i-1]+1) {
            ++currentLength;
        } else {
            maxLength = max(maxLength, currentLength);
            currentLength = 1;
        }
    }
    return max(maxLength, currentLength);
}

union-find

class Solution {
private:
    int size = 0;
    int *id, *sz;
    int root(int i) {
        while (i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }
    bool connected(int p, int q) {
        return root(p) == root(q);
    }
    void union_(int p, int q) {
        cout << "hi2\n";
        int i = root(p);
        int j = root(q);
        if (i == j) return;
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
    }

    int maxSz() {
        int res = 0;
        for (int i = 0; i < size; ++i)
            res = max(res, sz[i]);
        return res;
    }
public:
    int longestConsecutive(vector<int>& nums) {
        size = nums.size();
        id = new int[size];
        sz = new int[size];
        for (int i = 0; i < size; ++i) {
            id[i] = i;
            sz[i] = 1;
        }
        unordered_map<int, int> m;

        for (int i = 0; i < size; i++) {
            if (m.find(nums[i]) != m.end()) continue; // in case of duplicate
            // instore the position of current key
            m[nums[i]] = i;
            if (m.find(nums[i]+1) != m.end()) {
                union_(i, m[nums[i]+1]);
            }

            if (m.find(nums[i]-1) != m.end()) {
                union_(i, m[nums[i]-1]);
            }
        }

        return maxSz();
    }
};