一.題目

Longest Consecutive Sequence

Total Accepted: 33824 Total Submissions: 116565My Submissions

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.

Show Tags Have you met this question in a real interview? Yes No

Discuss

二.解題技巧

這道題有兩個技巧：

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

由於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(1)，因此沒想到利用哈希表來搜索與元素相鄰的數是否在數組中，使用哈希表是使得算法能夠保持在O(n)復雜度的一個必要條件。同時，一個數與其相鄰的數都在同一個連續子序列中，因此，可以在進行一次最大連續子序列查找的過程中將所有在該連續子序列中的元素進行標記，從而減少尋找最長連續子序列的這個過程，降低計算復雜度，使得這個尋找過程的計算復雜度為O(n)。 這道題為每一個元素設立標記位來記錄其所在的連續子序列已經進行處理的這個思路很巧妙，記得學習借鑒。