2014
11-19

# LeetCode-Longest Consecutive Sequence[数组]

### Longest Consecutive Sequence

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.

// Leet Code, Longest Consecutive Sequence
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
int longestConsecutive(const vector<int> &num) {
unordered_map<int, bool> used;

for (auto i : num) used[i] = false;

int longest = 0;

for (auto i : num) {
if (used[i]) continue;

int length = 1;

used[i] = true;

for (int j = i + 1; used.find(j) != used.end(); ++j) {
used[j] = true;
++length;
}

for (int j = i - 1; used.find(j) != used.end(); --j) {
used[j] = true;
++length;
}

longest = max(longest, length);
}

return longest;
}
};


// Leet Code, Longest Consecutive Sequence
// 时间复杂度O(n)，空间复杂度O(n)
// Author: @advancedxy
class Solution {
public:
int longestConsecutive(vector<int> &num) {
unordered_map<int, int> map;
int size = num.size();
int l = 1;
for (int i = 0; i < size; i++) {
if (map.find(num[i]) != map.end()) continue;
map[num[i]] = 1;
if (map.find(num[i] - 1) != map.end()) {
l = max(l, mergeCluster(map, num[i] - 1, num[i]));
}
if (map.find(num[i] + 1) != map.end()) {
l = max(l, mergeCluster(map, num[i], num[i] + 1));
}
}
return size == 0 ? 0 : l;
}

private:
int mergeCluster(unordered_map<int, int> &map, int left, int right) {
int upper = right + map[right] - 1;
int lower = left - map[left] + 1;
int length = upper - lower + 1;
map[upper] = length;
map[lower] = length;
return length;
}
};


Java代码:

'''

@author: gaotong
'''

class Solution:
# @param num, a list of integer
# @return an integer
def longestConsecutive(self, num):
numset = {}
for n in num:
numset[n] = True
ans = 1
clen = 1
for n in num:

if numset.get(n) == None:
continue
clen = 1
nextNum = n-1
while numset.get(nextNum) != None:
numset.pop(nextNum)
nextNum -= 1
clen += 1

nextNum = n+1
while numset.get(nextNum) != None:
numset.pop(nextNum)
nextNum += 1
clen += 1

if clen > ans:
ans = clen

return ans