数组中的最长连续子序列

[编程题]数组中的最长连续子序列

热度指数：37816 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $1 \le n \le 10^5$ ，数组中的值满足 $1\le val \le 10^8$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

示例1

输入

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

输出

示例2

输入

[1,1,1]

输出

备注:

算法知识视频讲解

编程小guy

我的思路是先排序，然后在一个一个比较，如果有重复的我就continue，不计入总数，这里排序的话，建议使用C语言的快速排序函数，很快而且很有效，如果自己写一个快排也是可以的，

/**
 * max increasing subsequence
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
#include <stdlib.h>
int inc(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int MLS(int* arr, int arrLen ) {
    // write code here
    qsort(arr,arrLen,sizeof(int),inc);
    int max=0;
    for(int i=0;i<arrLen;i++)
    {
        int sum=1;
        if(arr[i]+1==arr[i+1])
        {
            for(int j=i;j<arrLen-1;j++)
            {
                if(arr[j]+1==arr[j+1])
                {
                    sum+=1;
                }
                else if(arr[j]==arr[j+1])
                {
                    continue;
                }
                else
                {
                    i=j;
                    break;
                }
            }
        }
        if(max<sum) max=sum;
    }
    return max;
}

发表于 2021-12-04 09:32:30 回复(0)

犬灵

考虑到数据很密集的情况时，可以用hash记录每个数是否出现（优化版：位向量）、然后遍历找连续递增的seq并计数；理论复杂度O(n)，但测试数据规模实在是太小，所以这个方法的实际的时空效率极低……（还不如用STL<set>记录……）

static const int MAX_N = 100000000;
static int bv[MAX_N/32+1];

inline void setb(int i) { bv[i/32] |= (0x01 << (i % 32)); }
inline int getb(int i) { return (bv[i/32] >> (i % 32)) & 0x01; }

int MLS(int* arr, int arrLen) {
  memset(bv, 0x00, sizeof(bv));

  for (int i=0; i<arrLen; i++)
    setb(arr[i]);

  int len = 1, maxlen = 1;
  for (int i=2; i<MAX_N; i++)
    if (getb(i)) {
      if (getb(i-1)) len++;
    } else {
      if (len > maxlen) {
        maxlen = len;
        if (maxlen > MAX_N - i) break;  // stop early
      }
      len = 1;
    }
  
  return maxlen;
}

发表于 2021-08-11 16:16:42 回复(0)