leetcode 128. Longest Consecutive Sequence

Seawolf

1. Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
   
2. 
   
3. Your algorithm should run in O(n) complexity.
   
4. 
   
5. Example:
   
6. 
   
7. Input: [100, 4, 200, 1, 3, 2]
   
8. Output: 4
   
9. Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

复制代码

using priorityqueue

1. class Solution {
   
2.     public int longestConsecutive(int[] nums) {
   
3.         if(nums.length == 0) return 0;
   
4.         if(nums.length == 1) return 1;
   
5.         
   
6.         PriorityQueue<Integer> queue = new PriorityQueue<>();
   
7.         for(int i : nums) queue.offer(i);
   
8.         int max = Integer.MIN_VALUE;
   
9.         int count = 1;
   
10.         while(queue.size() > 1){
    
11.             int head = queue.poll();
    
12.             if(head == queue.peek() -1) count ++;
    
13.             else if (head == queue.peek()) continue;
    
14.             else count =1;
    
15.             
    
16.             if(count > max) max= count;
    
17.             
    
18.         }
    
19.         
    
20.         if(max == Integer.MIN_VALUE) return count;
    
21.         else return max;
    
22.     }
    
23. }

复制代码

sort array!

1. class Solution {
   
2.     public int longestConsecutive(int[] nums) {
   
3.         if(nums.length == 0) return 0;
   
4.         if(nums.length == 1) return 1;
   
5.         
   
6.         Arrays.sort(nums);
   
7.         int max = Integer.MIN_VALUE;
   
8.         int count = 1;
   
9.         for(int i = 1; i< nums.length; i++){
   
10.             if(nums[i] != nums[i-1]){
    
11.                 if(nums[i] - nums[i-1] == 1){
    
12.                     count++;
    
13.                 }else{
    
14.                     max = Math.max(max,count);
    
15.                     count =1;
    
16.                 }
    
17.             }
    
18.             
    
19.             
    
20.         }
    
21.         
    
22.         return Math.max(max,count);
    
23.     }
    
24. }

复制代码