首页 > 其他 > 详细

leetcode 23:longest-consecutive-sequence

时间:2020-08-16 15:09:59      阅读:72      评论:0      收藏:0      [点我收藏+]

题目描述

给定一个无序的整数类型数组,求最长的连续元素序列的长度。
例如:
给出的数组为[100, 4, 200, 1, 3, 2],
最长的连续元素序列为[1, 2, 3, 4]. 返回这个序列的长度:4
你需要给出时间复杂度在O(n)之内的算法
题目分析:
set会给放入的数组去重,本题是根据set的特性解题的。
代码如下:
 1  int longestConsecutive(vector<int>& num) {
 2        if(num.size() == 0)
 3            return 0;
 4         set<int> st(num.begin(),num.end());
 5         int count = 1;
 6         for(int i = 0;i < num.size();i++)
 7         {
 8             int temp = num[i];
 9             if(st.count(temp) == 0)
10                 continue;
11             int l = temp - 1;
12             int r = temp + 1;
13             while(st.count(l) != 0)
14             {
15                 st.erase(l);
16                 l--;
17             }
18             while(st.count(r) != 0)
19             {
20                 st.erase(r);
21                 r++;
22             }
23             count = max(count,r-l-1);
24         }
25         return count;
26     }

 

leetcode 23:longest-consecutive-sequence

原文:https://www.cnblogs.com/qingjiaowoxiaoxioashou/p/13512391.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!