☆打卡算法☆LeetCode 128. 最长连续序列 算法解析

恬静的小魔龙 发表于 2022/04/25 08:53:12 2022/04/25
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个未排序的整数数组,找出数字连续的最长序列的长度。”题目链接:来源:力扣(LeetCode)链接: 128. 最长连续序...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个未排序的整数数组,找出数字连续的最长序列的长度。”

题目链接:

来源:力扣(LeetCode)

链接: 128. 最长连续序列 - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:
输入: nums = [100,4,200,1,3,2]
输出: 4
解释: 最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4
示例 2:
输入: nums = [0,3,7,2,5,8,4,6,0,1]
输出: 9

二、解题

1、思路分析

本题可以枚举出所有数字,然后匹配地找出数字连续的最长连续序列。

最长连续序列必然有这样的规律:x,x+1,x+2,…,x+n,长度为n。

但是这样会导致算法时间复杂度到达O(n2),也就是一层枚举,一层匹配,无法满足题目要求。

可以使用哈希表存储数组中的数,这样查看一个数就可以达到O(1)的时间复杂度。

2、代码实现

代码参考:

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

image.png

3、时间复杂度

时间复杂度:O(n)

其中n为数组的长度。

空间复杂度:O(n)

哈希表存储数组中所有的数需要O(n)的空间。

三、总结

在代码中,需要先找到最长连续序列的第一个数x,这个可以判断哈希表中是否存在一个x-1的数。

如果存在就说明x-1为第一个数,那么就接着判断;如果不存在就可以进入内层循环。

也就是只有一个数是连续序列的第一个数的情况下才会进行内层循环,然后在内层循环中匹配连续序列中的数。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。