soulmachine/leetcode — pull request #12 by advancedxy (2014-01-11 16:15:15+00:00)
Title: 为longest consecutive sequence增加了一个worst case为O(n)的解法

hi,我看了一下你之前的实现,你的解法在worst case下是O(n^2)的.
比如对于[1,2,3,...,n]这样的sequence:
你要做的查询次数大致是1+2+3+...+n = O(n^2)(边角的查询忽略).
我下面提供的解法原始思路来自于http://discuss.leetcode.com/questions/1070/longest-consecutive-sequence 下的第一个回答.