Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Clarification
Your algorithm should run in O(n) complexity.
Example
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
思路
- 用全局变量count来记录每个连续sequence的长度
- 用全局变量maxLen来记录所有连续sequence的最长长度
- 先对数组排序
- 用2个指针，pre和cur
从1开始遍历数组
- 需要去重复，比如[-1， -1， 0 ，0，1， 1， 2]
while(cur < num.length && num[cur] == num[cur - 1]) {
pre++;
cur++;
}
此处必须保证cur < num.length
- 如果
num[pre] + 1 = num[cur]则说明是连续的sequence，更新pre, cur, maxLen
此处必须保证cur < num.length - 如果不连续，那么重置count, 更新pre, cur
public class Solution {
/*
* @param num: A list of integers
* @return: An integer
*/
public int longestConsecutive(int[] num) {
// write your code here
if (num == null || num.length == 0) {
return 0;
}
int pre = 0;
int i = 1;
int count = 1;
int maxLen = 1;
Arrays.sort(num);
for (; i < num.length; i++) {
while (i < num.length && num[i] == num[i - 1]) {
i++;
pre++;
}
if (i < num.length && num[pre] + 1 == num[i]) {
pre++;
count++;
maxLen = count > maxLen ? count : maxLen;
} else {
count = 1;
pre++;
}
}
return maxLen;
}
}
