注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex128 Longest Consecutive Sequence  

2015-05-31 16:46:47|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.

又见要求在线性复杂度内完成。按正常的思路,先快排序,然后从头开始扫一遍得到最大值,不过这样有个问题就是会出现重复的,如果用map这么数据结构就没有这个问题了,从头开始扫一遍。value就是当前值,如果map[value-1]有的话继续往后扫描,然后扫过的就清除掉就可以了,右边的也是一样的。见代码

class Solution {
public:
int longestConsecutive(vector<int>& nums) {
map<int, int> myMap;
int maxVal = 1; //最小就是1
int len = nums.size();
int i;
for (i = 0; i < len; i++)
myMap.insert(pair<int,int>(nums[i],1)); //开始的时候置为1
int left, right;// 左右两个方向搜索
int value;
for (i = 0; i < len; i++)
{
value = nums[i];
left = value - 1;
right = value + 1;
while (myMap[left])
{
myMap[left] = 0;//清除掉
left--;
}
while (myMap[right])
{
myMap[right] = 0;//清除掉
right++;
}
maxVal = myMax(maxVal,right-left-1);
}
return maxVal;
}
int myMin(int a,int b)
{
return a > b ? b : a;
}
int myMax(int a, int b)
{
return a > b ? a : b;
}
};


参考
http://blog.csdn.net/aivin24/article/details/23873943
  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017