Longest Consecutive Sequence

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

Clarification

Your algorithm should run in O(n) complexity.

Example

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

分析：

既然要求O(n) complexity，排序这种方法就放弃了。这里用了HashSet来保存每个数，然后从这个数开始，左右寻找是否有相邻的数。非常有新意的方法。

 public class Solution {

     public int longestConsecutive(int[] num) {

         if (num == null || num.length == ) return ;

         HashSet<Integer> hs = new HashSet<Integer>();

         for (int i = ; i < num.length; i++) {

             hs.add(num[i]);

         }

         int max = ;

         for (int i = ; i < num.length; i++) {

             if (hs.contains(num[i])) {

                 int count = ;

                 hs.remove(num[i]);

                 int low = num[i] - ;

                 while (hs.contains(low)) {

                     hs.remove(low);

                     low--;

                     count++;

                 }

                 int high = num[i] + ;

                 while (hs.contains(high)) {

                     hs.remove(high);

                     high++;

                     count++;

                 }

                 max = Math.max(max, count);

             }

         }

         return max;

     }

 }

参考请注明出处：cnblogs.com/beiyeqingteng/

巴特西

Longest Consecutive Sequence

最新文章

热门文章