【Longest Consecutive Sequence】cpp

题目：

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.

代码：

class Solution {

public:

    int longestConsecutive(vector<int> &num) {

        // hashmap record if element in num is visited

        std::map<int,bool> visited;

        for(std::vector<int>::iterator i = num.begin(); i != num.end(); ++i)

        {

            visited[*i] = false;

        }

        // search the longest consecutive

        unsigned int longest_global = ;

        for(std::vector<int>::iterator i = num.begin(); i != num.end(); ++i)

        {

            if(visited[*i]) continue;

            unsigned int longest_local = ;

            for(int j = *i+; visited.find(j) != visited.end(); ++j)

            {

                visited[j] = true;

                ++longest_local;

            }

            for(int j = *i-; visited.find(j) != visited.end(); --j)

            {

                visited[j] = true;

                ++longest_local;

            }

            longest_global = std::max(longest_global, longest_local+);

        }

        return longest_global;

    }

};

Tips:

1. 要想O(n), 而且无序，只能结合hashmap

2. 这里需要明确的一个逻辑是，通过hashmap前后访问，可以把包含当前元素的最大连同序列都找出来；而且访问过的元素不用再访问。

=======================================================

第二次过这道题，大体的思路能顺下来，但是疏忽了几个细节。AC代码如下：

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

            int global_longest = 1;

            // initialize map

            unordered_map<int, bool> visited;

            for ( int i=0; i<nums.size(); ++i ) visited[nums[i]]=false;

            // go one traversal

            for ( int i=0; i<nums.size(); ++i )

            {

                if ( visited[nums[i]] ) continue;

                visited[nums[i]] = true;

                int local_longest = 1;

                int curr = nums[i]-1;

                // search towards smaller direction

                while (    visited.find(curr)!=visited.end() )

                {

                    local_longest++;

                    visited[curr] = true;

                    curr--;

                }

                // search towards larger direction

                curr = nums[i]+1;

                while ( visited.find(curr)!=visited.end() )

                {

                    local_longest++;

                    visited[curr] = true;

                    curr++;

                }

                // update global longest

                global_longest = std::max(global_longest, local_longest);

            }

            return global_longest;

    }

};

tips:

1. 根据某个元素往‘前’、‘后’两个方向遍历之前，要先记得把该元素设置为访问过（即，visited[nums[i]] = true;）

2. 第一遍把while循环中的 visited[curr]=true都写成了visited[nums[i]]，这个纯属低级错误，不要再犯

3. 第一遍有一个逻辑上的错误：

　　"for ( int i=0; i<nums.size() && !visited[nums[i]]; ++i )"

本意是跳过已经访问过的元素。。。但是这么写如果遇到了访问过的元素，就不是跳过了，而是直接退出循环了。这是个思维的陷阱，记下来，下次不要再犯。

巴特西

【Longest Consecutive Sequence】cpp

最新文章

热门文章