LeetCode -- Longest Consecutive Sequence

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分別統計當前連續次數以及最大連續次數即可。


實現代碼：

public class Solution {
    public int LongestConsecutive(int[] nums) {
        if(nums.Length < 1){
    		return 0;
    	}
    	
        var lst = new SortedSet(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;
    }
}