作者：个信2602926933 | 来源：互联网 | 2023-10-16 11:32
Givenanunsortedarrayofintegers,findthelengthofthelongestconsecutiveelementssequence.Forexa
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
思路：先把大神的方法亮出来
use a hash map to store boundary information of consecutive sequence for each element; there 4 cases when a new element i reached:
1) neither i+1 nor i-1 has been seen: m[i]=1;
2) both i+1 and i-1 have been seen: extend m[i+m[i+1]] and m[i-m[i-1]] to each other;
3) only i+1 has been seen: extend m[i+m[i+1]] and m[i] to each other;
4) only i-1 has been seen: extend m[i-m[i-1]] and m[i] to each other.
int longestConsecutive(vector<int> &num) {
unordered_map<int, int> m;
int r = 0;
for (int i : num) {
if (m[i]) continue; //跳过重复
r = max(r, m[i] = m[i + m[i + 1]] = m[i - m[i - 1]] = m[i + 1] + m[i - 1] + 1); //如果新的数字把左右连起来了，则把该连起来的序列的第一个数m[i - m[i - 1]]和最后一个数字m[i + m[i + 1]] 设为新的长度！
}
return r;
}
下面是我自己写的，可谓血与泪的历史。
首先O(n)表示一定不能排序, 那如何获得左右邻接的信息呢。 肯定要用hash了。结果花了2个小时，写了一个超复杂的代码。虽然AC，但是.......唉...................................................
int longestConsecutive(vector<int> &num) {
//去重复
unordered_set<int> s;
for(int i = 0; i )
{
if(s.find(num[i]) == s.end())
s.insert(num[i]);
else
num.erase(num.begin() + (i--));
}
int maxlen = 0;
unordered_map<int, int> first; //记录每个连续序列的第一个数字在record中的哪个位置
unordered_map<int, int> last; //记录每个连续序列的最后一个数字在record中的哪个位置
vectorint>> record; //记录每个连续序列的第一个数字和最后一个数字是什么
for(int i = 0; i )
{
int pre, post;
unordered_map<int, int>::iterator f = first.find(num[i] + 1);
unordered_map<int, int>::iterator l = last.find(num[i] - 1);
if(f != first.end() && l != last.end())
{
pre = l->second;
post = f->second;
//修改hash表
last.erase(record[pre][1]);
first.erase(record[post][0]);
last[record[post][1]] = pre;
//修改记录的区间
record[pre][1] = record[post][1];
maxlen = (maxlen > record[pre][1] - record[pre][0] + 1) ? maxlen : record[pre][1] - record[pre][0] + 1;
record[post].clear();
}
else if(f != first.end())
{
post = f->second;
//修改hash
first.erase(record[post][0]);
first[num[i]] = post;
//修改区间
record[post][0] = num[i];
maxlen = (maxlen > record[post][1] - record[post][0] + 1) ? maxlen : record[post][1] - record[post][0] + 1;
}
else if(l != last.end())
{
pre = l->second;
last.erase(record[pre][0]);
last[num[i]] = pre;
record[pre][1] = num[i];
maxlen = (maxlen > record[pre][1] - record[pre][0] + 1) ? maxlen : record[pre][1] - record[pre][0] + 1;
}
else
{
record.push_back(vector<int>(2, num[i]));
first[num[i]] = record.size() - 1;
last[num[i]] = record.size() - 1;
maxlen = (maxlen > 1) ? maxlen : 1;
}
}
return maxlen;
}
【leetcode】Longest Consecutive Sequence（hard)☆
京公网安备 11010802041100号