Q:

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

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

A:

注意一点，题目说的序列长度是有几个连续+1的数。
然后题目不让用排序，用dict或者set做，这样就是O(N)复杂度，一个比较巧妙的地方：用当前元素减1的值试探集合，存在的话当前元素肯定不是其中一段最长连续子序列的起点，故跳过。

c++：

 1 class Solution {
 2 public:
 3     int longestConsecutive(vector<int>& nums) {
 4         unordered_set<int> st;
 5         for(int &num:nums){
 6             st.insert(num);
 7         }
 8         int res=0;
 9         for(int t:st){
10             if(st.count(t-1)){
11                 continue;
12             }
13             int cnt=0;
14             while(st.count(t)){
15                 ++t;
16                 ++cnt;
17             }
18             res=max(res,cnt);
19         }
20         return res;
21     }
22 };

python：

 1 class Solution:
 2     def longestConsecutive(self, nums: List[int]) -> int:
 3         nums=set(nums)
 4         res=1 if nums else 0
 5         for x in nums:
 6             if x-1 not in nums:
 7                 cur,y=1,x
 8                 while y+1 in nums:
 9                     cur+=1
10                     y+=1
11                 res=max(res,cur)
12         return res
13

原文链接: https://www.cnblogs.com/FdWzy/p/12288151.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/330331

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

128. 最长连续序列

Q:

A:

c++：

python：

相关推荐