LeetCode 热题 100 -- 128、最长连续序列

OK呀码友们今天也没有忘记继续Java的学习持之以恒我相信一定是每一个计算机学生都具备的品质吧哈哈哈哈哈什么你问我昨天怎么没有更新哈哈只是因为我昨天没有刷算法题并不代表我没有学习哦好了废话不多说今天依旧是哈希相关的题目一起看看吧。1、分析题目题目不长就是给我们一个未排序的整数数组找出最长连续序列返回它的长度即可特别要求了咱们设计的算法时间复杂度要是O(N)这可能是这道题的难点所在那么接下来分析一下不过朋友们请注意我不是什么算法大神发帖子是为了教学大家最华丽最高端的算法手段我只是一个小白我只想记录分享一下我在写每一道算法题时的“历程”也许我的思路能给一些同为小白的码友一些启发不过如果觉得我的思路太菜了太业余了也轻点喷哈那么我们开始吧。我最终是用了两种思路解决了这道题目。2、第一种思路说实话一开始我真的一下子还一头雾水没有什么思路我只能剖析一下题目看看有没有什么突破口。我想到既然是要找连续的序列给定的数组又是未排序的那么要不试试排个序之后通过遍历的方式解决。其实有一定的代码深度的码友肯定发现不对劲了题目不是要求你时间复杂度O(N)吗你调用排序后不都最少O(Nlog(N))了吗是的没错我承认你说的对但是我先是想能解决了再说[嘿嘿]。排序后我的思路是遍历nums随后用一个HashMap存储连续序列的开头作为key值就是这段序列的长度。随后再遍历一遍HashMap找出最大长度并输出。以下是我的代码实现请各位大佬赏脸瞅瞅代码乍一眼看上去还是比较长的哈。我也是经历了几次报错后修修改改最终拿出的这个版本[哭]。遍历时思路大致就是如果遍历到数组中有重复的数要跳过也就是去重其实有更好的办法随后就是记录连续序列的长度不过要注意索引越界的条件限制我就踩了坑的最后存进HashMap即可。不过虽然测试是通过的但是其实是不符合条件的。虽然遍历部分的时间复杂度是O(N)但是我是排了序的排序的时间复杂度是O(Nlog(N))所以代码的最终时间复杂度就是O(Nlog(N))还得再想想其他算法以下贴上提交记录。3、第二种思路随后我又陷入了沉思[沉默.....]。相信大家也都看出来了排序肯定行不通并且去重的部分也可以优化。随后就想到了Set底层的数据结构决定了其天然去重。那么既然不能排序那就只能通过优化遍历思路来尝试解决问题了。我们想到如果某个数N作为一个连续序列的开头那么对应Set里面就不会有N-1这个数的存在并且哈希表的优点就包括查询速率快那么可以遍历时试试直接查询集合中是否包含比当前值小的数如果有那么就跳过当前循环如果一个数满足作为开头的条件了就开始计算序列的长度用一个变量记录当前的最大序列长度然后不断更新最后返回即可。以下是我的代码实现这套代码的时间复杂度是O(N)满足要求。代码也更少更简洁或者说是更优美难度也不高重要的是要有对应的解题思路下面贴上提交记录截图我其实有一个可能比较外行的问题哈为什么这套代码的时间复杂度是比第一套要低的但运行时间却更多一些呢不知道有没有大佬看到我的帖子愿意给我解答一下呢4、总结今天这道题呢给我的感觉就是具体的问题要选用针对性的解决方案由于之前两张帖子写的都是用HashMap让我思维出现了定式导致我一开始这道题也要用这个错过了最佳的选择这点算是今天吸取到的教训。针对哈希相关的题目应该是告一段落了接下来应该就是针对双指针的相关题目了希望能有码友多支持我我也希望能在csdn遇见更多的同行者一起进步后续我找实习、面试以及找到实习后我也会在帖子中进行一些分享下次再见啦