[LeetCode] Longest Consecutive Sequence

Longest Consecutive SequenceFeb 14

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

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

因为有O(N)的限制。

因此用hash来搞。

 

 

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
    unordered_map<int, int> hash;
    vector<bool> flag(num.size(), false);
    for (int i = 0; i < num.size(); ++i) {
        hash[num[i]] = i;
    }

    int maxlen = 1;
    int less = 0, more = 0;
    for (int i = 0; i < num.size(); ++i) {
        if (flag[i]) continue;
        int tmp = num[i];
        auto it = hash.find(--tmp);
        less = 0;
        while (it != hash.end()) {
            ++less;
            flag[it->second] = true;
            it = hash.find(--tmp);
        }
        tmp = num[i];
        auto it2 = hash.find(++tmp);
        more = 0;
        while (it2 != hash.end()) {
            ++more;
            flag[it2->second] = true;
            it2 = hash.find(++tmp);
        }
        tmp = less + more + 1;
        maxlen = maxlen > tmp ? maxlen : tmp;
    }
    return maxlen;
}
};

 

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, bool> m;
        int len = num.size();
        for (int i = 0; i < len; i++) {
            m[num[i]] = false;
        }
        
        int res = 0;
        for (int i = 0; i < len; i++) {
            if (m[num[i]]) continue;
            int low = num[i], high = num[i];
            while (m.count(low) != 0) m[low] = true, low--;
            while (m.count(high) != 0) m[high] = true, high++;
            int t = high - low - 1;
            if (t > res) res = t;
        }
        return res;
    }
};