leetcode 128. Longest Consecutive Sequence
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:
Output: 4
Explanation: The longest consecutive elements sequence is . 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 != nums){
if(nums - nums == 1){
count++;
}else{
max = Math.max(max,count);
count =1;
}
}
}
return Math.max(max,count);
}
}
页:
[1]