【leetcode】Longest Consecutive Sequence

Question ：

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.

Anwser 1 ：

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<int, int> hmap;
        hmap.clear();
        int n = num.size();
        for(int i=0; i<n; i++){
            //hmap.insert(pair<int, int>(num[i], i));
            hmap[num[i]] = i;
        }
        int ans=0, cnt=0;
        map<int, int>::iterator it;
        for(int i=0; i<n; i++)
        {
            int cur = num[i];
            it = hmap.find(num[i]);     // value
            cnt++;
            if(it!=hmap.end())
            {
                map<int, int>::iterator iter;
                while(1){
                    iter = hmap.find(++cur);    // to larger value
                    if(iter == hmap.end())
                        break;
                    cnt++;    
                    hmap.erase(iter);
                }
                cur=num[i];
                while(1){
                    iter = hmap.find(--cur);    // to smaller value
                    if(iter == hmap.end())
                        break;
                    cnt++;    
                    hmap.erase(iter);
                }
                ans = cnt > ans ? cnt : ans;
            }
            cnt=0;      // init to count remaider value of hmap
        }
        return ans;
    }
};

注意点：

1） 采用map，value为map_key， index为map_value

2） 按value++， value--查找，找到了则从map移除（erase），减少for循环find的次数

3） for + while，时间复杂度最坏其实为O（n*n），但是仍然编译通过了...

Anwser 2 ：

class Solution {
public:
    int getCount(map<int, int> &hmap, int value, bool asc){
        int count = 0;
        
        while(hmap.find(value) != hmap.end()){
            hmap.erase(value);
            count++;
            
            if(asc){
                value++;
            } else {
                value--;
            }
        }
        return count;
    }


    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<int, int> hmap;
        hmap.clear();
        int n = num.size();
        for(int i=0; i<n; i++){
            //hmap.insert(pair<int, int>(num[i], i));
            hmap[num[i]] = i;
        }
        int ans=0, cnt=0;
        for(int i=0; i<n; i++)
        {
            int count = getCount(hmap, num[i], false) + getCount(hmap, num[i]+1, true);
            ans = count > ans ? count : ans;
        }
        return ans;
    }
};

注意点：

1） 改进了方法1

2） getCount（）找到则移除，count++，继续寻找下一个

3） count = getCount(hmap, num[i], false) + getCount(hmap, num[i]+1, true); 注意暗红色部分，加1为因为之前num[i]已经被移除了，因此找其上面一个value + 1

Anwser 3 ：

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<int, int> hmap;
        hmap.clear();
        int n = num.size();
        for(int i=0; i<n; i++){
            hmap.insert(pair<int, int>(num[i], 1));     // map will auto sort by key(num[i])
            //hmap[num[i]] = 1;
        }
        int ans = 1;        // min init
        int pre_k = 0;
        int pre_v = 0;
        
        map<int, int>::iterator it;
        for(it = hmap.begin(); it != hmap.end(); it++)
        {
            if(it == hmap.begin()) {
                pre_k = it->first;
                pre_v = it->second;
                continue;
            }
            
            if(it->first == pre_k + 1){
                it->second = pre_v + 1;
                ans = it->second > ans ? it->second : ans;
            }
            pre_k = it->first;
            pre_v = it->second;
            
        }
        return ans;
    }
};

注意点：

1） 方法2的进一步改进

2） 此方法最大的利用了map自动根据key（num[i]）排序，且value设为了1（起始值）