128. Longest Consecutive Sequence

  • 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
2
3
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.


方法一:

排序,一个个的查找

my code:

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

但是达到不了题目要求的O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.size()==0 || nums.size()==1) return nums.size();
sort(nums.begin(), nums.end());
int res=1;
int tmp=1;
int last = nums[0];
for(int i=1; i<nums.size(); i++){
if(nums[i]==nums[i-1])
continue;
else if(nums[i]==last+1){
tmp += 1;
last = nums[i];
}
else{
res = max(tmp, res);
tmp = 1;
last = nums[i];
}
}
res = max(res, tmp);
return res;
}
};

方法二:

使用set,然而效率仍然是o(nlogn)

https://discuss.leetcode.com/topic/16483/a-simple-c-solution-using-unordered_set-and-simple-consideration-about-this-problem

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int longestConsecutive(vector<int> &num) {
unordered_set<int> record(num.begin(),num.end());
int res = 1;
for(int n : num){
if(record.find(n)==record.end()) continue;
record.erase(n);
int prev = n-1,next = n+1;
while(record.find(prev)!=record.end()) record.erase(prev--);
while(record.find(next)!=record.end()) record.erase(next++);
res = max(res,next-prev-1);
}
return res;
}
};

my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int longestConsecutive(vector<int>& nums)
{
unordered_set<int> set(nums.begin(), nums.end());
int ret = 1;
for(auto &n: nums)
{
if(!set.count(n)) continue;
set.erase(n); // 删除元素
int pre=n-1, next=n+1;
while(set.count(pre)) set.erase(pre--); // set.count(n) 返回匹配给主键的元素的个数
while(set.count(next)) set.erase(next++);
ret = max(ret, next-pre-1);
}
return ret;
}
};

方法三:

使用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:

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

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

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

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

1
2
3
4
5
6
7
8
9
int longestConsecutive(vector<int> &num) {
unordered_map<int, int> m;
int r = 0;
for (int i : num) {
if (m[i]) continue;
r = max(r, m[i] = m[i + m[i + 1]] = m[i - m[i - 1]] = m[i + 1] + m[i - 1] + 1);
}
return r;
}

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, int> map;
int res = 0;
for(int num:nums){
if(map[num]) continue;
int len = map[num-1] + map[num+1] + 1;
map[num+map[num+1]] = len;
map[num-map[num-1]] = len;
map[num] = len;
res = max(res, len);
}
return res;
}
};

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
2
3
4
5
6
7
8
9
10
11
12
13
int longestConsecutive(const vector<int> &num) {
unordered_set<int> s(num.begin(), num.end()), searched;
int longest = 0;
for (int i: num) {
if (searched.find(i) != searched.end()) continue;
searched.insert(i);
int j = i - 1, k = i + 1;
while (s.find(j) != s.end()) searched.insert(j--);
while (s.find(k) != s.end()) searched.insert(k++);
longest = max(longest, k - 1 - j);
}
return longest;
}

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
2
3
4
5
6
7
8
9
10
def longestConsecutive(self, nums):
nums = set(nums)
best = 0
for x in nums:
if x - 1 not in nums:
y = x + 1
while y in nums:
y += 1
best = max(best, y - x)
return best

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

Python O(n) solution using sets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
# @param num, a list of integer
# @return an integer
def longestConsecutive(self, num):
num=set(num)
maxLen=0
while num:
n=num.pop()
i=n+1
l1=0
l2=0
while i in num:
num.remove(i)
i+=1
l1+=1
i=n-1
while i in num:
num.remove(i)
i-=1
l2+=1
maxLen=max(maxLen,l1+l2+1)
return maxLen

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:

  1. 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.
  2. 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int longestConsecutive(int[] num) {
int res = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int n : num) {
if (!map.containsKey(n)) {
int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
// sum: length of the sequence n is in
int sum = left + right + 1;
map.put(n, sum);

// keep track of the max length
res = Math.max(res, sum);

// extend the length to the boundary(s)
// of the sequence
// will do nothing if n has no neighbors
map.put(n - left, sum);
map.put(n + right, sum);
}
else {
// duplicates
continue;
}
}
return res;
}

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

My Java Solution using UnionFound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Solution {
public int longestConsecutive(int[] nums) {
UF uf = new UF(nums.length);
Map<Integer,Integer> map = new HashMap<Integer,Integer>(); // <value,index>
for(int i=0; i<nums.length; i++){
if(map.containsKey(nums[i])){
continue;
}
map.put(nums[i],i);
if(map.containsKey(nums[i]+1)){
uf.union(i,map.get(nums[i]+1));
}
if(map.containsKey(nums[i]-1)){
uf.union(i,map.get(nums[i]-1));
}
}
return uf.maxUnion();
}
}

class UF{
private int[] list;
public UF(int n){
list = new int[n];
for(int i=0; i<n; i++){
list[i] = i;
}
}

private int root(int i){
while(i!=list[i]){
list[i] = list[list[i]];
i = list[i];
}
return i;
}

public boolean connected(int i, int j){
return root(i) == root(j);
}

public void union(int p, int q){
int i = root(p);
int j = root(q);
list[i] = j;
}

// returns the maxium size of union
public int maxUnion(){ // O(n)
int[] count = new int[list.length];
int max = 0;
for(int i=0; i<list.length; i++){
count[root(i)] ++;
max = Math.max(max, count[root(i)]);
}
return max;
}
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public int longestConsecutive(int[] num) {
int longest = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0;i < num.length;i++){
// if there is no duplicates, these two lines can be commented
if(map.containsKey(num[i])) continue;
map.put(num[i],1);

int end = num[i];
int begin = num[i];
if(map.containsKey(num[i]+1))
end = num[i] + map.get(num[i]+1);
if(map.containsKey(num[i]-1))
begin = num[i] - map.get(num[i]-1);
longest = Math.max(longest, end-begin+1);
map.put(end, end-begin+1);
map.put(begin, end-begin+1);
}
return longest;
}
}
谢谢你,可爱的朋友。