LeetCode 128 Longest Consecutive Sequence

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:** [100, 4, 200, 1, 3, 2]
**Output:** 4
**Explanation:** The longest consecutive elements sequence is `[1, 2, 3, 4]`. Therefore its length is 4.

题目大意：

给出一个未排序的整数数组，找出最长的连续元素序列的长度。
如： 给出[100, 4, 200, 1, 3, 2]，最长的连续元素序列是[1, 2, 3, 4]。返回它的长度：4。

解题思路：

这是连通问题，如果用排序方法，很容易，但时间复杂度为O(nlogn)。考虑改进，因为连通集，容易想到HashMap，把每个元素加入到其中，
然后对每个元素进行相邻查找。相邻查找就是以此元素为中心，向上向下在Map查找，从而得到此元素的最大连续序列长度。查找过的元素
在Map中删除，以免重复计算。

第二遍

注意事项：

1. 先把所有数放入set，然后遍历每个数+1和-1删除。
2. 删除时候一定要在n+=1和n-=1之前删除

Python代码：

def longestConsecutive(self, nums: List[int]) -> int:
	nums_set, res = set(nums), 0
	for i in range(len(nums)):
		count, n = 1, nums[i] + 1
		while n in nums_set:
			count += 1
			nums_set.remove(n)
			n += 1
		n = nums[i] - 1
		while n in nums_set:
			count += 1
			nums_set.remove(n)
			n -= 1
		res = max(res, count)
	return res

注意事项：

1. 加入set之后的元素不能再内循环中删除，因为外循环是遍历每一个数，可能会遍历到删除的数，正确做法是用map的value来记录是否访问过。

Python代码：

def longestConsecutive(self, nums: List[int]) -> int:
	num_set = collections.Counter(nums)
	res = 0
	for n in nums:
		if num_set[n] == 0:
			continue
		max_len = 1
		num_set[n] = 0
		i = n + 1
		while i in num_set:
			num_set[i] = 0
			max_len += 1
			i += 1
		i = n - 1
		while i in num_set:
			num_set[i] = 0
			max_len += 1
			i -= 1
		res = max(res, max_len)
	return res

注意事项：

1. Java中在for循环中不能修改hashSet，所以只能用HashMap且value存boolean替代。HashMap表示此Map还是否含有该元素。

Java代码：

public int longestConsecutive(int[] nums) {
	int result = 0;
	HashMap<Integer,Boolean> hm = new HashMap<Integer,Boolean>();
	for(int i : nums)
		hm.put(i, true);
	
	Iterator it = hm.keySet().iterator();
	while(it.hasNext()){
		int key = (int)it.next();
		int i = key+1;
		int count = 1;
		while(hm.containsKey(i) && hm.get(i)){
			count++;
			hm.put(i, false);
			i++;
		}
		i = key-1;
		while(hm.containsKey(i) && hm.get(i)){
			count++;
			hm.put(i, false);
			i--;
		}
		if(count>result)
			result = count;
	}
	return result;
		
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。