search

soulmachine / leetcode

LeetCode题解，151道题完整版。
BSD 3-Clause "New" or "Revised" License
11.27k stars 3.43k forks source link

为longest consecutive sequence增加了一个worst case为O(n)的解法 #12

Closed advancedxy closed 10 years ago

advancedxy commented 10 years ago

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 下的第一个回答.

soulmachine commented 10 years ago

Good job, thanks :)