Leetcode 128最长连续序列
程序员文章站
2024-02-25 09:41:52
...
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
用map,hash也可以
class Solution
{
public:
int longestConsecutive(vector<int> &nums)
{
if(nums.size() == 0)
return 0;
set<int> s;
for(auto i : nums)
s.insert(i);
int ans = 1;
int cnt = 0;
int last = 0;
for(auto a : s)
{
if(cnt == 0)
{
cnt = 1;
}
else
{
if(a - last == 1)
{
ans = max(ans, ++cnt);
}
else
{
cnt = 1;
}
}
last = a;
}
return ans;
}
};
上一篇: Leetcode:128最长连续序列
下一篇: 最长回文子串——马拉车算法详解