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.

最初思路就是用一个hashset来纪录出现过的数字，然后再遍历set的过程中，对每一个元素的临近元素是否存在进行判断，再对临近元素是否有相邻元素进行判断，直至找到本轮的全部序列，然后判断该序列是否为最长序列。为了保证时间复杂度，每个元素被访问后需要被删除。

但采用java实现上述思路时，会出现问题，由于java中的迭代器都是fail-fast的实现方法，在迭代过程中不能删除collection中的元素，否则会报ConcurrentModificationException。为此，被迫采用map来纪录元素是否被访问过了。这里用hashmap，保证插入复杂度为O(1)。采用map后，性能比理想情况是差一些，但仍是O(n)的时间复杂度。

代码

import java.util.HashMap;
import java.util.Map;

public class LongestConsecutiveSequence {
	public int longestConsecutive(int[] num) {
		if (num == null) {
			return 0;
		}

		int max = 0;
		Map
  
    map = new HashMap
   
    (); for (int i = 0; i < num.length; ++i) { map.put(num[i], true); } for (Integer key : map.keySet()) { if (map.get(key)) { map.put(key, false); int left = 0; int p = key - 1; while (map.containsKey(p) && map.get(p)) { map.put(p, false); ++left; --p; } int right = 0; int q = key + 1; while (map.containsKey(q) && map.get(q)) { map.put(q, false); ++right; ++q; } max = Math.max(max, left + right + 1); } } return max; } }