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.
二.テーマ分析
この問題には2つのテクニックがあります.

ハッシュテーブルの挿入と検索の数の時間的複雑さはO(1)である.したがって、ハッシュテーブルを使用して配列を保存し、配列内の要素の検索が定数時間であることを保証することができる.

の1つの数とそれに隣接する数はいずれも同一の連続サブシーケンスにあるので、ある数が最長の連続サブシーケンス判定を開始したときに、同一の連続サブシーケンスにおける要素を判定の開始としてマークすることができ、その要素が存在する連続サブシーケンスが処理されているため、比較回数を大幅に少なくすることができる、計算の複雑さを低減する.

C++インプリメンテーションのハッシュテーブルは無秩序辞書タイプであるため、配列要素の値をキーワードとし、テクニック2の各要素のタグビットを各キーワードの値とすることができる.
配列の各要素について、連続するサブシーケンスが処理されたかどうかを判断し、処理された場合は、次の要素を直接処理します.まだ処理されていない場合は、それを中心として、隣接する数が存在するか否かを左に右に検索し、存在する場合は長さに1を加算し、その要素のタグ位置ビットを、その要素が存在する連続サブシーケンスが処理されたことを示し、隣接する数が存在しないまでシーケンスの長さを記録し、次に、次の要素を処理します.この方法によれば、最長連続サブシーケンスの検索中に各要素は1回しかアクセスされないため、計算の複雑さはO(n)である.
ハッシュ・テーブルを作成する過程で、計算の複雑さもO(n)であり、したがって、アルゴリズム全体の時間的複雑さはO(n)+O(n)=O(n)である.
三.サンプルコード

class Solution
{
public:
    int longestConsecutive(vector<int> &num)
    {
        // get the size of the num
        int Size = num.size();
        // build the hash_table
        unordered_map<int, bool> 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)にすることができる.