Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given
The longest consecutive elements sequence is
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.
Solution: intuitively, use hash table to get O(n) complexity.
However, the following code is stupid since it continues search duplicated items and the complexity becomes O(n^2).
In order to avoid additional searching, the following code deletes items from the hash table once it has been checked. Since each element will only be accessed once, and the amortized cost of insert/delete/find operations for hash table is O(1), the overall time complexity is linear.
Comments
Post a Comment