128. 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.

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

给一个未排序数组,找到一个最长的连续数组,返回其长度.

====

思路:

利用一个hash表,存储已经扫描的数组元素,

对数组中每一个curr元素,都必须在hash表中向前查找,向后查找,找出此nums[curr]过在连续数组。

maxlength = max(maxlength,length);

===

code:

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

        unordered_map<int,bool> hash_used;

        for(auto i:nums){

            hash_used[i] = false;

        }

        int longest = ;

        for(auto i:nums){

            if(hash_used[i])

                continue;

            int length = ;

            hash_used[i] = true;

            for(int j = i+;hash_used.find(j)!=hash_used.end();j++){

                hash_used[j] = true;

                length++;

            }

            for(int j = i-;hash_used.find(j)!=hash_used.end();j--){

                hash_used[j] = true;

                length++;

            }

            longest = max(longest,length);

        }//for

        return longest;

    }

};

巴特西

128. Longest Consecutive Sequence

最新文章

热门文章