整数序列中最长的连续序列个数（LeetCode-128）-白红宇

整数序列中最长的连续序列个数（LeetCode-128）

阅读量：344 次

发布时间：2019-03-04

本文共 1063 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到一个整数序列中最长的连续子序列。连续子序列在这里指的是在排序后的序列中，连续递增的数字序列，其中每个数字比前一个大1。

方法思路

排序：首先对序列进行排序。排序可以将所有连续的数字排列在一起，使得后续处理更加容易。

遍历排序后的数组：遍历排序后的数组，统计每个数字与前一个数字的差是否为1。如果是，则当前连续子序列长度加一；否则，重置连续子序列长度为1。

记录最长连续子序列长度：在遍历过程中，记录遇到的最大连续子序列长度。

这种方法的时间复杂度是 O(n log n)，因为排序操作的时间复杂度是 O(n log n)，而遍历数组的时间复杂度是 O(n)，总体复杂度为 O(n log n)。

解决代码

#include 
   
    #include 
    
     using namespace std;int longestConsecutive(vector
     
      & nums) {    if(nums.size() == 0) return 0;    sort(nums.begin(), nums.end());    int max_len = 1;    int current_len = 1;    for(int i = 1; i < nums.size(); ++i) {        if(nums[i] == nums[i-1] + 1) {            current_len++;        } else {            current_len = 1;        }        if(current_len > max_len) {            max_len = current_len;        }    }    return max_len;}