2014年4月25日 星期五

[LeetCode] Longest Consecutive Sequence

Problem:
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: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;
   }
}

沒有留言:

張貼留言