首页 > 数据结构 > Hash表 > LeetCode-Longest Consecutive Sequence(哈希)
2014
06-10

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.

大意:对一个无序的数组,找出其中最长的连续子序列。

题目链接:https://oj.leetcode.com/problems/longest-consecutive-sequence/

排序的话至少要O(nlgn) 的复杂度。O(n)的复杂度,目前只找到了使用hash来解决的方案,add, remove, contains 等方法的复杂度都是 O(1),因此两次遍历的操作复杂度为 O(n)。

public class Solution {
    public int longestConsecutive(int[] num) {
        Set<Integer> set = new HashSet<Integer>();
		int max = 1;
		for (int e : num)
			set.add(e);
		for (int e : num) {
			int left = e - 1;
			int right = e + 1;
			int count = 1;
			while (set.contains(left)) {
				count++;
				set.remove(left);
				left--;
			}
			while (set.contains(right)) {
				count++;
				set.remove(right);
				right++;
			}
			max = Math.max(count, max);
		}
		return max;
    }
}

参考:http://www.programcreek.com/2013/01/leetcode-longest-consecutive-sequence-java/


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。