LeetCode -- Longest Consecutive Sequence
题目描述：
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
就是在一个没有排序好的序列中找到最大的连续子序列。
思路：
1.本题关键是使用一种高效的数据结构，拿完成这个排序。选择SortedSet，用于内部实现为平衡树,因此增删查时间复杂度均为O(logN)
2.使用c和max分别统计当前连续次数以及最大连续次数即可。
实现代码：
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
就是在一个没有排序好的序列中找到最大的连续子序列。
思路：
1.本题关键是使用一种高效的数据结构，拿完成这个排序。选择SortedSet，用于内部实现为平衡树,因此增删查时间复杂度均为O(logN)
2.使用c和max分别统计当前连续次数以及最大连续次数即可。
实现代码：
public class Solution {
public int LongestConsecutive(int[] nums) {
if(nums.Length < 1){
return 0;
}
var lst = new SortedSet<int>(nums);
var max = 1;
var c = 1;
int? pre = null;
foreach(var n in lst){
if(!pre.HasValue){
pre = n;
continue;
}
else{
if(n - pre == 1){
c++;
if(c > max){
max = c;
}
}
else{
c = 1;
}
pre = n;
}
}
return max;
}
}