专栏首页米扑专栏【leetcode】Longest Consecutive Sequence

【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(起始值)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode】Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    阳光岛主
  • 【leetcode】Palindrome Partitioning II

    Given a string s, partition s such that every substring of the partition is a pa...

    阳光岛主
  • 【leetcode】3Sum Closest

    Given an array S of n integers, find three integers in S such that the sum is cl...

    阳光岛主
  • C语言和C++混合开发简单版本计算器

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • Java案例-判断随机整数是否是素数

    Java案例-判断随机整数是否是素数 ? 判断随机整数是否是素数 产生 100 个0-999 之间的随机整数,然后判断这100 个随机整数哪些是素数,哪些不是?...

    奋斗蒙
  • 欢聚时代笔试题,滴滴出行编程题

    intel 笔试: 1.单链表逆置,双向链表删除 2.层次遍历二叉树 3.rand4()生成rand9() 4.非常多的各种指针操作。

    用户1539362
  • POJ-3461-Oulipo

    ACM模版 描述 ? 题解 KMPKMP 入门级题目,模板题。 代码 #include <iostream> const int MAXN = 1e4 + 1...

    f_zyj
  • HDU 3368 Reversi

    http://acm.hdu.edu.cn/showproblem.php?pid=3368 题意:模拟黑白棋,下一步黑手最大可以转化多少个白旗 分析:暴力  ...

    用户1624346
  • 历届试题 连号区间数

    如果区间[L, R] 里的所有元素(即此排列的第L个到第R个元素)递增排序后能得到一个长度为R-L+1的“连续”数列,则称这个区间连号区间。

    AI那点小事
  • 1064 朋友数 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051

扫码关注云+社区

领取腾讯云代金券