leetcode筆記：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.

二. 題目分析

這道題有兩個技巧：

哈希表插入和查找一個數的時間復雜度為O(1)；因此，可以使用哈希表來保存數組，以保障對於數組中的元素的查找是常量時間； 一個數與它相鄰的數都在同一個連續子序列中，因此，可以在某個數開始進行最長連續子序列判斷的時候，可以將與它在同一連續子序列中的元素標記為不作為判斷的開始，因為該元素所在的連續子序列處理過了，這樣就可以大大較少比較次數，降低計算復雜度；

由於C++實現中的哈希表是一個無序字典類型，因此，可以將數組元素的值作為關鍵字，技巧2中每個元素的標記位作為每一個關鍵字的值。

對於數組中的每一個元素，先判斷其所在連續子序列是否已經處理過了，如果已經處理過了，則直接處理下一個元素；如果還沒處理過，則以其為中心，向左向右查找是否有相鄰的數存在數組中，如果存在，就將長度加1，並將該元素的標記位置位，表示該元素所在的連續子序列已經處理過了，一直查找下去，直到相鄰的數字不存在數組中為止，記錄序列的長度，然後處理下一個元素。按照這個方法，在進行最長連續子序列查找的過程中，每個元素只被訪問一次，因此計算復雜度為O(n)。

在創建哈希表的過程中，計算復雜度也為O(n)，因此，整個算法的時間復雜度為O(n)+O(n)=O(n)。

三. 示例代碼

class Solution
{
public:
    int longestConsecutive(vector &num)
    {
        // get the size of the num
        int Size = num.size();
        // build the hash_table
        unordered_map HashTable;
        for (int Index = 0; Index < Size; Index++)
        {
            int Tmp = num[Index];
            HashTable[Tmp] = false;
        }
        // find the longest consecutive sequence
        int LongestNumber = 1;
        for (int Index = 0; Index < Size; Index++)
        {
            int Tmp = num[Index];
            if (HashTable[Tmp])
            {
                continue;
            }
            int TmpSequence = 1;
            while (HashTable.find(++Tmp) != HashTable.end())
            {
                HashTable[Tmp] = true;
                TmpSequence++;
            }
            Tmp = num[Index];
            while (HashTable.find(--Tmp) != HashTable.end())
            {
                HashTable[Tmp] = true;
                TmpSequence++;
            }
            if (LongestNumber < TmpSequence)
            {
                LongestNumber = TmpSequence;
            }
        }
        return LongestNumber;
    }
};

四. 小結

該題可以在進行一次最大連續子序列查找的過程中將所有在該連續子序列中的元素進行標記，從而減少尋找最長連續子序列的這個過程，降低計算復雜度，使得這個尋找過程的計算復雜度為O(n)。