首页 > 代码库 > 【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.
想法比较直接,就是先排序,然后慢慢去里面遍历找连续的element。
需要注意这么几点:
1.如果数组里只有1个元素,那么直接回复1.
2.一定要考虑duplicate的情况,因为比如排序后为1,1,1,2,3,一定要跳过重复的元素。
程序如下:
package testAndfun; import java.util.Arrays; public class LongestConsecutiveSequence { public static void main(String[] args){ LongestConsecutiveSequence lcs = new LongestConsecutiveSequence(); int[] input = {1,0,-1,1}; System.out.println(lcs.longestConsecutive(input)); } public int longestConsecutive(int[] num) { if(num.length<=1) return num.length; int count =1 ; int tmp=1; Arrays.sort(num); //System.out.println(Arrays.toString(num)); int i=0; while(i<num.length-1){ if(num[i]==num[i+1]-1) tmp++; if(num[i]==num[i+1]){ if(tmp>count){ count = tmp; } i++; continue; } if(num[i]!=num[i+1]-1 || i==num.length-2){ if(tmp>count) { count = tmp; } tmp =1; } i++; } return count; } }
【Leetcode】Longest Consecutive Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。