2014年5月7日星期三

Loop Solution - Longest Consecutive Sequence - loop and cut

The idea is to remove all duplicates since it is not useful for consecutive, don't let it bother the main logic. So for each element in the array, loop all neighbors from the pre processed HASH SET, count and compare it with result… REMEMBER remove the parsed/processed elements from the SET, to cut unnecessary elements which guarantees the O(n) solution.

REMEMBER count both ways, ++ and --

public class Solution {
    public int longestConsecutive(int[] num) {
        Set<Integer> process = new HashSet<Integer>();
        for(int i = 0; i < num.length; i++){
            process.add(num[i]);
        }
        int index = 0;
        int result = 1;
        while(index < num.length){
            if(process.contains(num[index])){
                int count = 1;
                process.remove(num[index]);
                for(long i = num[index] + 1; i <= Integer.MAX_VALUE; i++){
                    if(process.contains((int)i)){
                        count++;
                        process.remove((int)i);
                    }else{
                        break;
                    }
                }
                for(long j = num[index] - 1; j >= Integer.MIN_VALUE; j--){
                    if(process.contains((int)j)){
                        count++;
                        process.remove((int)j);
                    }else{
                        break;
                    }
                }
                if(count > result){
                    result = count;
                }
            }
            index++;
        }
        return result;
    }
}

没有评论: