Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given
The longest consecutive elements sequence is
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:O(n)
public class Solution { public int longestConsecutive(int[] num) { HashSet<Integer> hashset = new HashSet<Integer>(); for(int t:num) hashset.add(t); int max = 0; for(int t:num){ if(hashset.contains(t)) max = Math.max(max,findLongest(hashset, t, true) + findLongest(hashset, t-1, false) ); } return max; } public int findLongest(HashSet<Integer> hashset, int num, boolean flag){ int ret = 0; while(hashset.contains(num)){ ret++; hashset.remove(num); if(flag){ num++; }else{ num--; } } return ret; } }
沒有留言:
張貼留言