最长连续序列 - 中等难度

*************

c++

topic： 128. 最长连续序列 - 力扣（LeetCode）

*************

See the topic:

when it comes to array, use sort first.

as is mentioned before, sort is a standard library in c++. Here review the usage of sort again

The default is to sort in ascending order:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1};
    
    std::sort(vec.begin(), vec.end());
    
    for (int num : vec) {
        std::cout << num << " ";
    }
    return 0;
}

and the result is 

1 2 3 4 5

however, if I write some lambda code, it will returen as wish:

#include <algorithm>
#include <vector>
#include <iostream>

bool compare(int a, int b) {
    return a > b; // 降序排序
}

int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1};
    
    std::sort(vec.begin(), vec.end(), compare);
    
    for (int num : vec) {
        std::cout << num << " ";
    }
    return 0;
}

the result is:

5 4 3 2 1

and in this case, just use the basic function, In ascending order.

if the nums is empty, just return 0;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        
        int n = nums.size();
        if (n == 0) return 0;

      // do sth. here

    }
};

then comes sort and initialize the max length and current length.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        
        int n = nums.size();
        if (n == 0) return 0;

        // initialize the length
        // use sort
        sort(nums.begin(), nums.end());
        int max_length = 1;
        int current_length = 1;

        // do sth. here

    }
};

if nums[i] == nums[i - 1], continue；

and if nums[i] == nums[i - 1] + 1; current length = current length + 1;

this is eazy to turn into the code:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        
        int n = nums.size();
        if (n == 0) return 0;

        // initialize the length
        // use sort
        sort(nums.begin(), nums.end());
        int max_length = 1;
        int current_length = 1;

        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] == nums[i - 1] + 1) {
                current_length += 1;
            } else {
                max_length = max(max_length, current_length);
                current_length = 1;
            }
        }

        return max(max_length, current_length);
    }
};