[leetcode]128. Longest Consecutive Sequence最长连续序列

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

题目

给定一个数组，计算将其排序以后能形成的最长连续序列。

思路

如果允许O(nlogn)的复杂度，那么可以先排序。以下是naive 的先排序的代码实现

 1 class Solution {
 2     public int longestConsecutive(int[] nums){
 3         Arrays.sort(nums);
 4         if(nums == null || nums.length == 0) return 0;
 5         int result = 1;
 6         int length = 1;
 7 
 8         for (int i = 1; i < nums.length; i++ ) {
 9             if(nums[i] == nums[i-1] + 1 ){
10                 length ++;
11             }else if (nums[i] == nums[i-1]){
12                 continue;
13             }else{
14                 length = 1;
15                 
16             }
17             result = Math.max(result, length);
18         }
19 
20      return  result;
21     }
22 }

再思考：

可是本题要求O(n)。
由于序列里的元素是无序的，又要求O(n)，想到用哈希set。

代码

 1 public int longestConsecutive(int[] nums) {
 2         if(nums.length == 0) return 0;
 3         Set<Integer> set = new HashSet<Integer>();
 4         int max = 1;
 5         for(int num : nums)
 6             set.add(num);
 7         for(int i = 0; i < nums.length; i++){
 8             if(!(set.contains(nums[i] - 1))){
 9                 int currentSequence = 0;
10                 int next = nums[i];
11                 while(set.contains(next)){
12                     currentSequence++;
13                     max = Math.max(max, currentSequence);
14                     next++;
15                 }
16             }
17         }
18         
19         
20         return max;
21     }