- 35.7%

https://leetcode.com/problems/longest-consecutive-sequence/?tab=Description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

1 | For example, |

Your algorithm should run in O(n) complexity.

方法一：

排序，一个个的查找

my code:

先排序，然后依次查找，同时注意出现相同数字的处理。

但是达到不了题目要求的O（n）

1 | class Solution { |

方法二：

使用set，然而效率仍然是o（nlogn）

A simple C++,solution using unordered_set.And simple consideration about this problem

I have seen a lot of discussion about this problem.In my opinion,it is not correct to use set(which is ordered),because very time we insert an element to a ordered set,it will cost O(n),so the total complexity is O(nlogn),which violates the request of the problem.So here we use an unordered_set,and one is enough.

Besides,to think about this problem,one principle issue we should realize is that usually when we want to reduce the time complexity,we have to increase the space complexity.In this case,if we want to access an element within O(1),we have to use hash table.

1 | class Solution { |

my code：

1 | class Solution { |

方法三：

使用hashmap

m[i]表示i为中间值的一段的长度的大小，初始为0

https://discuss.leetcode.com/topic/5333/possibly-shortest-cpp-solution-only-6-lines

Possibly shortest cpp solution, only 6 lines.

use a hash map to store boundary information of consecutive sequence for each element; there 4 cases when a new element i reached:

neither i+1 nor i-1 has been seen: m[i]=1;

both i+1 and i-1 have been seen: extend m[i+m[i+1]] and m[i-m[i-1]] to each other;

only i+1 has been seen: extend m[i+m[i+1]] and m[i] to each other;

only i-1 has been seen: extend m[i-m[i-1]] and m[i] to each other.

1 | int longestConsecutive(vector<int> &num) { |

我的代码实现：

1 | class Solution { |

https://discuss.leetcode.com/topic/6408/13-line-c-solution

13-line C++ solution

Thought I would share it here. May be useful for some one. The algorithm itself is pretty straightforward. But it benefited quite much from the neat expression of C++ idioms. Comments are appreciated!

1 | int longestConsecutive(const vector<int> &num) { |

#### python

https://discuss.leetcode.com/topic/15383/simple-o-n-with-explanation-just-walk-each-streak

Simple O(n) with Explanation - Just walk each streak

First turn the input into a set of numbers. That takes O(n) and then we can ask in O(1) whether we have a certain number.

Then go through the numbers. If the number x is the start of a streak (i.e., x-1 is not in the set), then test y = x+1, x+2, x+3, … and stop at the first number y not in the set. The length of the streak is then simply y-x and we update our global best with that. Since we check each streak only once, this is overall O(n). This ran in 44 ms on the OJ, one of the fastest Python submissions.

1 | def longestConsecutive(self, nums): |

https://discuss.leetcode.com/topic/10678/python-o-n-solution-using-sets

Python O(n) solution using sets

1 | class Solution: |

#### java

https://discuss.leetcode.com/topic/6148/my-really-simple-java-o-n-solution-accepted

My really simple Java O(n) solution - Accepted

We will use HashMap. The key thing is to keep track of the sequence length and store that in the boundary points of the sequence. For example, as a result, for sequence {1, 2, 3, 4, 5}, map.get(1) and map.get(5) should both return 5.

Whenever a new element n is inserted into the map, do two things:

- See if n - 1 and n + 1 exist in the map, and if so, it means there is an existing sequence next to n. Variables left and right will be the length of those two sequences, while 0 means there is no sequence and n will be the boundary point later. Store (left + right + 1) as the associated value to key n into the map.
- Use left and right to locate the other end of the sequences to the left and right of n respectively, and replace the value with the new length.

Everything inside the for loop is O(1) so the total time is O(n). Please comment if you see something wrong. Thanks.

1 | public int longestConsecutive(int[] num) { |

https://discuss.leetcode.com/topic/29286/my-java-solution-using-unionfound

My Java Solution using UnionFound

1 | public class Solution { |

https://discuss.leetcode.com/topic/9088/o-n-hashmap-java-solution

O(n) HashMap Java Solution

Use a hashmap to map a number to its longest consecutive sequence length, each time find a new consecutive sequence, only the begin number and end number need to be modified.

1 | public class Solution { |