128. Longest Consecutive Sequenc

题目128. 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.

1,BFS

public class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        
        int max = 0;
        Map<Integer,Integer> memory = new HashMap<Integer,Integer>();
        for(int num : nums){
            if(!memory.containsKey(num)){
                int left = memory.containsKey(num - 1) ? memory.get(num-1) : 0;
                int right = memory.containsKey(num + 1) ? memory.get(num+1) : 0;
                
                int sum = left + right + 1;
                memory.put(num,sum);
                max = max > sum ? max : sum;
                
                memory.put(num-left,sum);
                memory.put(num+right,sum);
            }
        }
        
        return max;
    }
}

2,BFS+并查集

public class Solution {
    
    private int[] parents;
    public void initUnionFind(int[] nums){
        if(nums == null){
            return;
        }
        
        parents = new int[nums.length];
        for(int i=0, len=nums.length; i<len; i++){
            parents[i] = i;
        }
    }
    
    public int find(int idx){
        while(idx != parents[idx]){
            parents[idx] = parents[parents[idx]];
            idx = parents[idx];
        }
        return idx;
    } 
    
    public void union(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot != qRoot){
            parents[qRoot] = pRoot;
        }
    }
    
    public int maxSectionNum(){
        int[] counter = new int[parents.length];
        int max = 0;
        for(int i=0,len=parents.length; i<len; i++){
            int root = find(parents[i]);
            counter[root]++;
            max = max > counter[root] ? max : counter[root];
        }
        return max;
    }
    
    
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        
        Map<Integer,Integer> memory = new HashMap<Integer,Integer>();
        initUnionFind(nums);
        for(int i=0, len=nums.length; i<len; i++){
            if(!memory.containsKey(nums[i])){
                memory.put(nums[i],i);
                if(memory.containsKey(nums[i]-1)){
                    union(i,memory.get(nums[i]-1));
                }
                
                if(memory.containsKey(nums[i]+1)){
                    union(i,memory.get(nums[i]+1));
                }
            }
        }
        
       return maxSectionNum();
    }
}