当前位置：网站首页>[数组]NC95 数组中的最长连续子序列-较难

[数组]NC95 数组中的最长连续子序列-较难

2022-07-23 23:19:00 【51CTO】

NC95 数组中的最长连续子序列

知识点并查集数组

描述

给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

数据范围：，数组中的值满足

要求：空间复杂度，时间复杂度

示例1

输入：

       
       [100,4,200,1,3,2]
      
1.

返回值：

示例2

输入：

返回值：

题解

排序+统计

思路：

先将数组排序，然后统计连续的数字。注意，如果连续的2个数字相等，此时不应该重置连续长度。

和该解法类似的还有使用set存放所有元素然后进行统计，或者使用hash表统计~~

代码如下：

       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       MLS(
       
       vector
       
       <
       
       int
       
       > 
       
       &
       
       arr)
       
{
       
       if (
       
       arr.
       
       size() 
       
       <= 
       
       1)
       
  {
       
       return 
       
       arr.
       
       size();
       
  }
       
       std::sort(
       
       arr.
       
       begin(), 
       
       arr.
       
       end());
       
       int 
       
       ans 
       
       = 
       
       1;
       
       int 
       
       len 
       
       = 
       
       1;
       
       for (
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       < 
       
       arr.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       if (
       
       arr[
       
       i 
       
       - 
       
       1] 
       
       + 
       
       1 
       
       == 
       
       arr[
       
       i])
       
    {
       
       len
       
       ++;
       
       ans 
       
       = 
       
       std::max(
       
       len, 
       
       ans);
       
       continue;
       
    }
       
       else 
       
       if (
       
       arr[
       
       i 
       
       - 
       
       1] 
       
       == 
       
       arr[
       
       i])
       
    {
       
       continue;
       
    }
       
       else
       
    {
       
       len 
       
       = 
       
       1;
       
    }
       
  }
       
       return 
       
       ans;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.