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.
思路
先对数组排序，然后用DP
1 public class Solution { 2 public int longestConsecutive(int[] num) { 3 Arrays.sort(num); 4 int curLength = 1; 5 int maxLength = 1; 6 7 for(int i = 1; i < num.length; i++){ 8 if(num[i] == num[i - 1]) 9 continue; 10 else if(num[i] - num[i - 1] == 1){ 11 curLength ++; 12 maxLength = maxLength > curLength ? maxLength : curLength; 13 } 14 else 15 curLength = 1; 16 }//for 17 18 return maxLength; 19 } 20 }
原文：http://www.cnblogs.com/luckygxf/p/4248340.html