LeetCode_Longest Consecutive Sequence

一.题目

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

Discuss

二.解题技巧

这道题有两个技巧：

1.哈希表插入和查找一个数的时间复杂度为O(1)；因此，能够使用哈希表来保存数组。以保障对于数组中的元素的查找是常量时间。

2.一个数与它相邻的数都在同一个连续子序列中，因此。能够在某个数開始进行最长连续子序列推断的时候，能够将与它在同一连续子序列中的元素标记为不作为推断的開始。由于该元素所在的连续子序列处理过了，这样就能够大大较少比較次数，减少计算复杂度；

因为C++实现中的哈希表是一个无序字典类型，因此，能够将数组元素的值作为keyword，技巧2中每个元素的标记位作为每个keyword的值。

对于数组中的每个元素，先推断其所在连续子序列是否已经处理过了，假设已经处理过了，则直接处理下一个元素；假设还没处理过，则以其为中心。向左向右查找是否有相邻的数存在数组中，假设存在，就将长度加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(1)，因此没想到利用哈希表来搜索与元素相邻的数是否在数组中，使用哈希表是使得算法可以保持在O(n)复杂度的一个必要条件。

同一时候，一个数与其相邻的数都在同一个连续子序列中。因此，可以在进行一次最大连续子序列查找的过程中将全部在该连续子序列中的元素进行标记。从而降低寻找最长连续子序列的这个过程。降低计算复杂度。使得这个寻找过程的计算复杂度为O(n)。

这道题为每个元素设立标记位来记录其所在的连续子序列已经进行处理的这个思路非常巧妙，记得学习借鉴。

版权全部，欢迎转载，转载请注明出处。谢谢