请教一个Leetcode上的算法题

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.
-------------------------------------------------------------------------------
以下是我的想法，但我略糊涂这想法是不是o(n)的。
先扫一遍，每个数放入Hashset

针对Hashset里的每个现存的数,往上找最多n个,如果不在Hashset里的话就停下来，如果在的话就把该数从Hashset里删了。往下找类似。
比如我从4开始找，发现5就没了，所以往上找停止。然后往下找，发现3，2，1都在Hashset里，把它们删除，然后记录这个长度，与当前最长的比较。

略糊涂我这个想法是不是o(n)的

没太懂lz的想法，要不你写写代码出来看看

ryancooper 发表于 2013-3-5 16:43
没太懂lz的想法，要不你写写代码出来看看

哦，我理解了好像

楼主的想法确实是O(n)的复杂度，因为：
扫描数据，放入hashset中：O(n)
在hashset中查值时，每个元素最多被访问到1次，因此复杂度也为O(n)，但是对hashset进行初始化时，复杂度为O(m)，m为hashset的容量一般来说，m会选取为n的2到3倍
因此总的复杂度也就是O(n)

仔细思考一下设计hashfunction和factorload吧。

反正现在随便弄个hash都喊O（n)，真面试起来倒无所谓了。

楼主这是不对的。
hash顶多期望是1，insert和delete都不能保证O(1)，更别说如果用open addressing来实现了。
这里用位图就行了，其他流程你思路是对的。

好困想睡觉 发表于 2013-3-5 05:19
楼主这是不对的。
hash顶多期望是1，insert和delete都不能保证O(1)，更别说如果用open addressing来实现了 ...

位图的话复杂度为O(k)吧，k为输入数组的范围

zengxinzhy 发表于 2013-3-5 17:33
位图的话复杂度为O(k)吧，k为输入数组的范围

遍历时以输入为索引去遍历，而不用遍历整个位图，复杂度就等于n了。

好困想睡觉 发表于 2013-3-5 05:42
遍历时以输入为索引去遍历，而不用遍历整个位图，复杂度就等于n了。

遍历的时候是可以这么做，但为位图开辟一片空间以后首先是需要初始化的，把位图中的所有数据都设为0，这一步是无论如何也避免不了的O(k)

zengxinzhy 发表于 2013-3-5 05:06
楼主的想法确实是O(n)的复杂度，因为：
扫描数据，放入hashset中：O(n)
遍历hashset时，每个元素最多被到 ...

Sorry, 开始的时候把楼主的遍历方法理解错了，把关于m的分析跳过