Sunday, April 16, 2017

Longest Consecutive Sequence c++

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.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int max = 0;
        int cnt = 0;
        if (nums.size() == 0 ) return 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i< nums.size(); i++) {
            if (nums[i]+1 == nums[i+1]) {
                cnt++;
            } else if (nums[i+1] > nums[i]){
                if (cnt>max) max = cnt;
                cnt = 0;
            }
        }
        if (cnt>max) max = cnt;
        return max+1;
    }
};

No comments:

Post a Comment