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.

    二. 題目分析

    這道題有兩個(gè)技巧：

哈希表插入和查找一個(gè)數(shù)的時(shí)間復(fù)雜度為O(1)；因此，可以使用哈希表來(lái)保存數(shù)組，以保障對(duì)于數(shù)組中的元素的查找是常量時(shí)間； 一個(gè)數(shù)與它相鄰的數(shù)都在同一個(gè)連續(xù)子序列中，因此，可以在某個(gè)數(shù)開(kāi)始進(jìn)行最長(zhǎng)連續(xù)子序列判斷的時(shí)候，可以將與它在同一連續(xù)子序列中的元素標(biāo)記為不作為判斷的開(kāi)始，因?yàn)樵撛�素所在的連續(xù)子序列處理過(guò)了，這樣就可以大大較少比較次數(shù)，降低計(jì)算復(fù)雜度；

    由于C++實(shí)現(xiàn)中的哈希表是一個(gè)無(wú)序字典類型，因此，可以將數(shù)組元素的值作為關(guān)鍵字，技巧2中每個(gè)元素的標(biāo)記位作為每一個(gè)關(guān)鍵字的值，

leetcode筆記：Longest Consecutive Sequence

。

    對(duì)于數(shù)組中的每一個(gè)元素，先判斷其所在連續(xù)子序列是否已經(jīng)處理過(guò)了，如果已經(jīng)處理過(guò)了，則直接處理下一個(gè)元素；如果還沒(méi)處理過(guò)，則以其為中心，向左向右查找是否有相鄰的數(shù)存在數(shù)組中，如果存在，就將長(zhǎng)度加1，并將該元素的標(biāo)記位置位，表示該元素所在的連續(xù)子序列已經(jīng)處理過(guò)了，一直查找下去，直到相鄰的數(shù)字不存在數(shù)組中為止，記錄序列的長(zhǎng)度，然后處理下一個(gè)元素。按照這個(gè)方法，在進(jìn)行最長(zhǎng)連續(xù)子序列查找的過(guò)程中，每個(gè)元素只被訪問(wèn)一次，因此計(jì)算復(fù)雜度為O(n)。

    在創(chuàng)建哈希表的過(guò)程中，計(jì)算復(fù)雜度也為O(n)，因此，整個(gè)算法的時(shí)間復(fù)雜度為O(n)+O(n)=O(n)。

    三. 示例代碼

<code class="hljs cpp">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;    }};</int,></int></code>

    四. 小結(jié)

    該題可以在進(jìn)行一次最大連續(xù)子序列查找的過(guò)程中將所有在該連續(xù)子序列中的元素進(jìn)行標(biāo)記，從而減少尋找最長(zhǎng)連續(xù)子序列的這個(gè)過(guò)程，降低計(jì)算復(fù)雜度，使得這個(gè)尋找過(guò)程的計(jì)算復(fù)雜度為O(n)，

電腦資料

《leetcode筆記：Longest Consecutive Sequence》(http://www.solarmaxlimited.com)。