leetcode 128. Longest Consecutive Sequence

Seawolf

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

using priorityqueue

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return 1;
        
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i : nums) queue.offer(i);
        int max = Integer.MIN_VALUE;
        int count = 1;
        while(queue.size() > 1){
            int head = queue.poll();
            if(head == queue.peek() -1) count ++;
            else if (head == queue.peek()) continue;
            else count =1;
            
            if(count > max) max= count;
            
        }
        
        if(max == Integer.MIN_VALUE) return count;
        else return max;
    }
}

sort array!

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return 1;
        
        Arrays.sort(nums);
        int max = Integer.MIN_VALUE;
        int count = 1;
        for(int i = 1; i< nums.length; i++){
            if(nums[i] != nums[i-1]){
                if(nums[i] - nums[i-1] == 1){
                    count++;
                }else{
                    max = Math.max(max,count);
                    count =1;
                }
            }
            
            
        }
        
        return Math.max(max,count);
    }
}