Longest Consecutive Sequence
Total Accepted:6466Total
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;
}
分享到:
相关推荐
Consecutive Sequence 7 Two Sum Hash,夹逼均可 8 3Sum Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next Permutation 公式 13 Permutation Sequence 公式 14 Valid ...
LMS Longest Monotonically Increasing Sequence Algorithm
Longest Consecutive Sequence Two Sum 3Sum 3Sum Closest 4Sum Remove Element Move Zeroes Next Permutation Permutation Sequence Valid Sudoku Trapping Rain Water Rotate Image Plus One Climbing Stairs Set ...
前端工程师面试
java lru leetcode SDE-问题 标准 SDE 问题列表 第一天:(数组) 日 问题陈述 解决方案 困难 使用的数据结构 使用的算法 时间复杂度 空间复杂度 ...Longest Consecutive Sequence Longest Subarray w
leetcode正方体收藏TakeUforward-SDE_180 要了解整个列表和其他内容,如项目、简历、如何进行面试……观看整个视频: 在以下位置找到展示位置系列: ...Consecutive Sequence Longest Subarray with 0 sum 给定
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
最长连续序列 描述 给定一个未排序的整数数组,请找出最长的连续元素序列的长度。 好吧,假设该任务仅与步长等于1的序列有关。 例如: 给定exampleArray = [100, 4, 200, 1, 3, 2] 100,4,200,1,3,2 [100, 4, ...
给定两个序列X={X1, X2,···,Xm}和Y={Y1, Y2,···,Yn},找出X和Y的最长公共子序列(Longest Common Sequence)。 比如字符串X:{BDCABA};字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
关于Longest Common Subsequences演算法
java解决动态规划中最长公共子序列(longest common sequence)问题
Codewars实践 解决方案 3k 问题/卡塔 解决方案 4k 问题/卡塔 解决方案 5k 问题/卡塔 解决方案 6- 问题/卡塔 解决方案 7- 问题/卡塔 解决方案
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
为此,针对代码同源性检测结构化匹配进行了研究,在LCS(longest common sequence)算法中融入了跳变信息保留、结构边界划分、窗口搜索、计数重置、有效序列界定等逻辑,用于Token摘要的结构化信息匹配,提出了一种...
Longest Ordered Subsequence,算法分析与设计,C语言程序
Longest Common Ancestor classic ppt...
最长公共子序列演示程序,算法分析与设计,动态规划算法
求最长公共子序列,求最长公共子序列!!!