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來記錄每個連續(xù)sequence的長度
- 用全局變量maxLen來記錄所有連續(xù)sequence的最長長度
- 先對數(shù)組排序
- 用2個指針肃叶，pre和cur
從1開始遍歷數(shù)組
- 需要去重復，比如[-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]則說明是連續(xù)的sequence咳燕，更新pre, cur, maxLen
此處必須保證cur < num.length - 如果不連續(xù)勿决，那么重置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;
}
}
