Longest Consecutive Sequence
Total Accepted: 6466 Total
Submissions: 24260My Submissions
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.
3到4星级难度。
考点：活用hash表
利用?:操作可以简化让程序更加简洁。
注意：
1 数组中的数字会有重复，不要重复处理数据。
2 利用hash数据结构存储新增的数字，更新连续数字两边的边界值。
3 统计hash表中的最大值。
int longestConsecutive(vector<int> &num)
{
unordered_map<int, int> mii;
int len = 0;
for (int i = 0; i < num.size(); i++)
{
if (!mii.count(num[i]))
{
int a = mii.count(num[i]-1)? mii[num[i]-1]:0;
int b = mii.count(num[i]+1)? mii[num[i]+1]:0;
mii[num[i]] = a+b+1;
if(b) mii[num[i]+b] = a+b+1;
if(a) mii[num[i]-a] = a+b+1;
len = max(len, a+b+1);
}
}
return len;
}
//2014-2-18 update
int longestConsecutive(vector<int> &num)
{
unordered_map<int, int> ump_ii;
int ans = 1;
for (int i = 0; i < num.size(); i++)
{
if (ump_ii.count(num[i])) continue;
ump_ii[num[i]] = 1;
int pos1 = 0;
if (ump_ii.count(num[i]+1))
{
pos1 = ump_ii[num[i]+1];
ump_ii[num[i]] = pos1+1;
ump_ii[num[i]+pos1] = ump_ii[num[i]];
}
if (ump_ii.count(num[i]-1))
{
int pos2 = ump_ii[num[i]-1];
ump_ii[num[i]] += pos2;
ump_ii[num[i]+pos1] = ump_ii[num[i]-pos2] = ump_ii[num[i]];
}
ans = max(ans, ump_ii[num[i]]);
}
return ans;
}