首页 > 代码库 > 【LeetCode】Longest Consecutive Sequence
【LeetCode】Longest Consecutive Sequence
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(key,pre)记录每个节点的前驱节点,然后用这个map来像树的层序遍历一样得到树的最大深度
一直超时,题目要求的是O(n)一直超时
public class NSolution { public int longestConsecutive(int[] num) { Map<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int j=0;j<num.length;j++){ map.put(num[j], Integer.MAX_VALUE); } for(int i=0;i<num.length;i++){ int temp = num[i]; if(map.containsKey(temp-1)){ map.put(temp, temp-1); } } Queue<Integer> queue = new LinkedList<Integer>(); Queue<Integer> tempqueue = new LinkedList<Integer>(); queue.offer(Integer.MAX_VALUE); int count=-1; while(!queue.isEmpty()){ int temp = queue.peek(); queue.poll(); Set<Integer> set = map.keySet(); Iterator<Integer> it = set.iterator(); while(it.hasNext()){ int tt = it.next(); if(map.get(tt)==temp){ tempqueue.add(tt); } } if(queue.isEmpty()){ count++; queue=tempqueue; tempqueue=new LinkedList<Integer>(); } } return count; } }
后面想到用空间换时间,用java的bitset类型,但是当处理[2011444,145555,5,1111111]的时候明显会超时,bieset
可以用来处理比较密集的数据,但是不适合用来处理比较离散的数据
public class BitNSolution { public int longestConsecutive(int[] num) { if(num.length==0) return 0; if(num.length==1) return 1; int max=num[0]; int min=num[0]; for(int i=1;i<num.length;i++){ if(num[i]>=max) max=num[i]; if(num[i]<min) min=num[i]; } if(min<0) min=-min; if(min==0) min=1; if(max==0) max=1; BitSet bs = new BitSet(max); BitSet mbs = new BitSet(min); for(int i=0;i<num.length;i++){ if(num[i]<0){ mbs.set(-num[i],true); }else{ bs.set(num[i], true); } } int re=0; int count=0; for(int k=mbs.size()-1;k>0;k--){ if(mbs.get(k)){ count++; if(count>re) re=count; }else{ count=0; } } for(int j=0;j<bs.size();j++){ if(bs.get(j)){ count++; if(count>re) re=count; }else{ count=0; } } return re; } }
经过观察可以发现,4和3 2 1 的最大连续长度是一样的,因此在找到其中任何一个数的最大连续序列后,可以在map中将这些序列所包含的
数全部删除,以避免重复编列。
时间复杂度为O(n) + O(n) + O(序列长度总和) 近似可以认为是O(n)
public class Solution { public int longestConsecutive(int[] num) { Map<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i=0;i<num.length;i++) map.put(num[i], 1); int re =1; for(int j=0;j<num.length;j++){ if(!map.containsKey(num[j])) continue; map.remove(num[j]); int temp = num[j]+1; int val = 1; while(map.containsKey(temp)){ map.remove(temp); val++; temp++; } temp = num[j]-1; while(map.containsKey(temp)){ map.remove(temp); temp--; val++; } if(val>re) re=val; } return re; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。