首页 > 代码库 > LeetCode: Longest Consecutive Sequence [128]
LeetCode: Longest Consecutive Sequence [128]
【题目】
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.
【题意】
给定一个未排序的整数数组,找长度最长的连续整数串序列,并返回长度。 复杂度要求O(n)【思路】
O(n)不一定是one pass, 脑子里总是有这么种固定思维,自己给自己挖了个坑。O(kn)也是O(n), 只要k是常数。要找连续串,又不能排序,那我们要构造一个类列表结构把连续的数串起来。那么怎么串呢?很显然,给定一个数N,那我们需要知道他的前一个数prev和它的后一个数next是否存在,如果存在我们就可以串到prev或者next, 如果不存在则连续串就结束鸟。我们用一个map来表示这种前后继关系。
prev=N-1; next=N+1; 假定N是存在于数组中的,则map[N]=1
如果prev也在数组中,则map[prev]=1, 否则map[prev]=0
如果next也在数组中,则map[next]=1, 否则map[next]=0
我们对数组进行两遍扫描:
第一遍扫描是我们生成前后关系map
第二遍扫描利用前后关系恢复连续串,恢复过程中对应数的map[i]都置为0,避免重复恢复
【代码】
class Solution { public: int longestConsecutive(vector<int> &num) { int size=num.size(); if(size==0)return 0; //第一遍扫描建立前后关系map map<int, int> exist; for(int i=0; i<size; i++){ exist[num[i]]=1; if(exist[num[i]-1]!=1)exist[num[i]-1]=0; if(exist[num[i]+1]!=1)exist[num[i]+1]=0; } //第二遍扫描 int maxLength=0; for(int i=0; i<size; i++){ if(exist[num[i]]==1){ //恢复串 int length=1; int number=num[i]-1; while(exist[number]==1){length++; exist[number]=0; number--;} number=num[i]+1; while(exist[number]==1){length++; exist[number]=0; number++;} if(length>maxLength)maxLength=length; } } return maxLength; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。