开发者社区> lancel0t> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

算法题丨Longest Consecutive Sequence

简介: 描述 Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
+关注继续查看

描述

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.

示例

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

算法分析

难度:高
分析:给定未排序的整型数组,找到数值连续的元素,并返回连续元素的最大长度。
思路:首先考虑一般的思路,可以将数组先排序,然后遍历数组元素,判断是否连续,返回最大连续元素的个数,这样的话,循环的复杂度为O (n),排序的复杂度为O (nlgn),算法的整体复杂度为O (nlgn),并不满足题目要求的复杂度。所以,该算法题目的难点是如何采用O (n)的算法。
再考虑使用哈希表来存储元素,因为哈希表提供了O (1)复杂度的Contains方法,以便我们快速的访问元素:
 1. 首先,我们将数组元素构造成哈希表,并定义变量longestStreak=0,用来记录最大连续元素的个数;
 2. 遍历哈希表,判断当前元素num-1,是否存在在哈希表中:
  a). 如果不存在,不用处理,继续遍历哈希表下一个元素;
  b). 如果存在,说明有比当前元素小1的值,则定义currentNum=当前元素,定义currentStreak=1,表示currentNum作为开始比较的元素,刚开始的连续元素个数为1;
  c). 开始后续比较,如果哈希表存在currentNum+1的元素,表示当前元素currentNum有后续相邻的元素,连续的元素为之前最大连续元素次数+1,开始下个一个元素比较,即currentNum+1;
  d). 后续比较结束后,将本次循环获得的currentStreak作为本次循环记录的最大连续元素个数,记录本次最大连续次数currentStreak和之前最大连续次数longestStreak的最大值到longestStreak,并进入下一个循环遍历;
 3. 循环遍历结束后,返回最大连续次数longestStreak;

代码示例(C#)

public int LongestConsecutive(int[] nums)
{
    var numSet = new HashSet<int>(nums);
    //记录最大连续元素个数
    int longestStreak = 0;

    foreach (int num in numSet)
    {
        //存在跟当前元素连续的值
        if (!numSet.Contains(num - 1))
        {
            int currentNum = num;
            int currentStreak = 1;

            //每匹配到后面连续的元素,当前最大连续元素个数+1
            while (numSet.Contains(currentNum + 1))
            {
                currentNum += 1;
                currentStreak += 1;
            }

            //最大连续元素个数取当前最大连续元素和记录的最大连续元素个数两者最大者
            longestStreak = Math.Max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}                                          

复杂度

  • 时间复杂度O (n).
  • 空间复杂度O (n).

附录

img_8f0a90f3cbaa0e044fb8bf7b13c4317b.jpe

文章作者:原子蛋
文章出处:https://www.cnblogs.com/lizzie-xhu/
个人网站:https://www.lancel0t.cn/
个人博客:https://blog.lancel0t.cn/
微信公众号:原子蛋Live+
扫一扫左侧的二维码(或者长按识别二维码),关注本人微信公共号,获取更多资源。
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Microsoft Naive Bayes 算法——三国人物身份划分
原文:Microsoft Naive Bayes 算法——三国人物身份划分   Microsoft朴素贝叶斯是SSAS中最简单的算法,通常用作理解数据基本分组的起点。这类处理的一般特征就是分类。这个算法之所以称为“朴素”,是因为所有属性的重要性是一样的,没有谁比谁更高。
1113 0
[LeetCode] Binary Tree Longest Consecutive Sequence
Problem Description: Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from so...
645 0
mysql批量修改存储引擎和字符集
mysql批量修改存储引擎和字符集
0 0
+关注
lancel0t
资深软件工程师/架构师,毕业于武汉大学-国际软件学院-软件工程硕士专业。
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Needle in the Haystack—User Behavior Anomaly Detection for Information Security
立即下载
Cost-based Query Optimization
立即下载
低代码开发师(初级)实战教程
立即下载