首页 > ACM题库 > LeetCode > LeetCode-Longest Consecutive Sequence[数组]
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.

标签: Array
分析

如果允许$O(n \log n)$的复杂度,那么可以先排序,可是本题要求$O(n)$。

由于序列里的元素是无序的,又要求$O(n)$,首先要想到用哈希表。

用一个哈希表 {unordered_map<int, bool> used}记录每个元素是否使用,对每个元素,以该元素为中心,往左右扩张,直到不连续为止,记录下最长的长度。

代码1

// 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;
    }
};

代码2

// 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