首页 > 代码库 > Problem Longest Consecutive Sequence

Problem Longest Consecutive Sequence

2024-07-10 03:19:04   221人阅读

Problem Description:

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.

 

Solution:

 1     public int longestConsecutive(int[] num) { 2         Set<Integer> set = new HashSet<Integer>(); 3          4         for (int e : num) { 5             set.add(e); 6         } 7         int max = 1; 8         for (int e : num) { 9             int left = e -1;10             int right = e + 1;11             int count = 1;12 13             while (set.contains(left)) {14                 count++;15                 set.remove(left);16                 left--;17             }18 19             while (set.contains(right)) {20                 count++;21                 set.remove(right);22                 right++;23             }24 25             max = Math.max(max, count);26         }27 28         return max;29     }

 


联系
我们