描述
输入一个乱序的连续数列，输出其中最长连续数列长度，要求算法复杂度为 O(n) 。
输入
54,55,300,12,56
输出
3
输入样例
100,4,200,1,3,2
54,55,300,12
1
5,4,3,2,1
1,2,3,4,5,6
输出样例
4
2
1
5
6
解析：这里的最长连续数列不是最大上升/下降子序列，而是连续整数数列，又因为有复杂度O(n)限制，不能通过排序后计数的方式。
查阅资料之后发现了一种使用map关联容器来高效查找同时计数的算法。
[小米OJ] 4. 最长连续数列 - Rh's blog - CSDN博客
#include <bits/stdc++.h>
using namespace std;
int main()
{
string input;
while (cin >> input)
{
istringstream iss(input);
string temp;
vector<int> vec;
map<int, int> mapping;
int maxNum = -1;
while (getline(iss, temp, ','))
{
vec.push_back(atoi(temp.c_str()));
mapping[atoi(temp.c_str())] = 0;
}
for (auto c : vec)
{
if (mapping[c] == 0)
{
mapping[c] = 1;
if (mapping.count(c - 1))
{
mapping[c] += mapping[c - 1];
}
if (mapping.count(c + 1))
{
mapping[c] += mapping[c + 1];
}
maxNum = maxNum > mapping[c] ? maxNum : mapping[c];
}
}
cout << maxNum << endl;
}
return 0;
}
但是这种算法对于一些特定顺序的数列计算无效，如5，3，4，2。原因是在判断过程中只判断了前后各一个数及其连续数列长度，而又不能对错误的数列计数进行更新，所以这种算法是无效的。
求最长连续数列长度 - weixin_33946020的博客 - CSDN博客
之后结合了这篇博客中的算法思想，将计算连续数列的过程以当前分析的数为中心分成左右两个数列，并在查找计数的过程中将成功计入的数用erase弹出容器（避免重复计数），最后将左右两个数列相加，得到当前数所在连续队列的队长。最终利用set关联容器的高效查找能力完成了这个题目。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string input;
while (cin >> input)
{
istringstream iss(input);
string temp;
//存放数列
vector<int> vec;
//用set容器高效查找关键字，‘关键字’对应数的具体数值的字符串形式
set<int> setting;
int maxNum = -1;
while (getline(iss, temp, ','))
{
vec.push_back(atoi(temp.c_str()));
setting.insert(atoi(temp.c_str()));
}
for (auto &c : vec)
{
if(setting.count(c))
{
int leftlength = 0;
int rightlength = 0;
int leftKey = c - 1;
int rightKey = c + 1;
while (setting.count(leftKey)) //map.count(k)，返回关键字为k的元素的数量，这里判断是否存在
{
setting.erase(leftKey); //map.erase(k),删除关键字为k的元素。可以作为返回值(size_type)记录所删除元素的数量
leftlength++;
leftKey -= 1;
}
while (setting.count(rightKey))
{
setting.erase(rightKey);
rightlength++;
rightKey += 1;
}
maxNum = maxNum > (leftlength+rightlength+1) ? maxNum : (leftlength+rightlength+1);
}
}
cout << maxNum << endl;
}
return 0;
}
