Longest Consecutive Sequence @LeetCode

2014-11-24 08:44:39 · 作者: · 浏览: 0
又是一道Hashtable或者HashSet的空间换时间的题!
package Level3;  
  
import java.util.HashSet;  
import java.util.Set;  
  
/** 
 * Longest Consecutive Sequence 
 *  
 * 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. 
 *  
 */  
public class S132 {  
  
    public static void main(String[] args) {  
        int[] num = {0,0};  
        System.out.println(longestConsecutive(num));  
    }  
  
    // 遇到不能排序又要复杂度O(n)有序的问题,只能增加空间复杂度,用hashset或者hashtable  
    public static int longestConsecutive(int[] num) {  
        Set set = new HashSet();  
          
        for (int i : num) {  
            set.add(i);  
        }  
        int max = 0;  
          
        for(int i=0; i