首页 > 试题广场 >

数组中的最长连续子序列

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

热度指数：36175 时间限制：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]

输出

备注:

算法知识视频讲解

Java

牛客839384289号

public int MLS (int[] arr) {
    // write code here
    Arrays.sort(arr);
    int res=0;
    for(int i=0;i<arr.length;i++){
        int num=1;
        while(i+1<arr.length && arr[i+1]-arr[i]<=1){
            if(arr[i]+1==arr[i+1]){
                num++;
            }
            i++;
        }
        res=Math.max(res,num);
    }
    return res;
}

发表于 2024-03-09 16:30:26 回复(0)

Java

梁山教父

import java.util.*;


public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
     //1 2 3 4 100 200
    public int MLS (int[] arr) {
        // write code here
        Arrays.sort(arr);
        int max=1;
        int count=1;
        for(int i=1;i<arr.length;i++){
            if(arr[i]==arr[i-1]){
                continue;
            }
            if(arr[i]-arr[i-1]==1){
                count++;
            }else{
                count=1;
            }
            max=Math.max(count,max);
        }
        return max;
    }
}

发表于 2023-05-14 15:53:50 回复(0)

Java

代码需要写注释？

***就不能给个1，2，2，2，3这样一眼能看出来的例子，还非要自己想，简单题伪装成难题是因为需要自己想案例是吧，牛客这点真的不如力扣

发表于 2022-03-03 16:32:48 回复(0)

Java

可爱抱抱呀😥

//运行时间：343ms 占用内存：117184KB
import java.util.*;
public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        // write code here
        int count=0;
        int ans=0;
        boolean has[]=new boolean[100000006];
        for(int i=0;i<arr.length;i++){has[arr[i]]=true;}
        for(int i=1;i<=100000;i++){
            if(has[i]){count++;}
            else{
                ans=Math.max(ans,count);
                count=0;
            }
        }
        return Math.max(ans,count);
    }
}

发表于 2021-12-29 14:10:13 回复(0)

Java

雷欧尼桑

public int MLS (int[] arr) {
    Arrays.sort(arr);
    int count = 1;
    int max = 1;
    for (int i = 1; i < arr.length; i++) {
        switch (arr[i] - arr[i - 1]) {
            case 0:
                continue;
            case 1:
                count++;
                max = (max > count) ? max : count;
                continue;
            default:
                count = 1;
        }
    }
    return max;
}

发表于 2021-12-25 21:42:43 回复(0)

Java

躺王

public int MLS (int[] arr) {
        // write code here
        Arrays.sort(arr);
        int max = 0;
        int count = 0;
        for(int i=0;i<arr.length;i++){
            count = 1;
            while(i+1<arr.length){
                if(arr[i+1]==arr[i]+1)
                    count++;
                else if(arr[i+1]!=arr[i])
                    break;
                i++;
            }
            max = Math.max(max,count);   
        }
        return max;
    }

发表于 2021-11-26 16:16:38 回复(0)

Java

牛客388923860号

// 换个方向，不连续的时候记录，代码会简单许多
public int MLS (int[] arr) {
        int ans = 0;
        Arrays.sort(arr);
        int l = 0;
        int repeat = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) {
                repeat++;
                continue;
            }
            if (arr[i] != arr[i - 1] + 1) {
                ans = Math.max(ans, i - l - repeat);
                l = i;
                repeat = 0;
            }
        }
        // 最后一个元素
        if (l != arr.length - 1) {
            ans = Math.max(ans, arr.length - l - repeat);
        }
        return ans;
    }

发表于 2021-11-07 16:00:49 回复(0)

Java

刻苦的大熊猫在度假

java

1.首先对数组进行排序（快排：O(nlogn)）；

2.使用map记录每个元素的位置，map的value值取List<Integer>是因为数组中有重复值

3.动态规划使用dp[i]表示以arr[i]为结尾的元素所能表示的最长连续子序列的长度，通过前面的map可以得到arr[i]-1对应的下标（如果数组中存在arr[i]-1,假设下标为index），那么dp[i]可以通过dp[i] = dp[index]+1获得

4.数组中的最长连续子序列长度为dp[i]的最大值

import java.util.*;
public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        // write code here
        // 先对arr排序
        Arrays.sort(arr);
        // <arr[i], {index1,index2...}>   // 存在值相同的情况
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        int len = arr.length;
        for(int i=0;i<len;i++){
            int num = arr[i];
            if(map.keySet().contains(num)){
                map.get(num).add(i);
            }else{
                List<Integer> list = new ArrayList<Integer>();
                list.add(i);
                map.put(num, list);
            }
        }
        if(len == 0) return 0;
        int max = 1;
        // dp[i] 表示以arr[i]为结尾的元素所能表示最长连续子序列长度
        int[] dp = new int[len];
        // 初始时，每个arr[i]结尾的元素所能表示的最长连续子序列长度为1
        Arrays.fill(dp,1);
        for(int i=1;i<len;i++){
            int curValue = arr[i];
            if(map.keySet().contains(curValue-1)){
                List<Integer> indexList = map.get(curValue-1);
                for(int index : indexList){
                    dp[i] = Math.max(dp[index]+1,dp[i]);
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}

发表于 2021-10-12 21:26:29 回复(0)

Java

牛气嘣嘣

判特：数组为空，或长度小于2，直接返回len
定义ans，并且定义tmp作为ans的临时值，用来更新ans；
数组排序
如果当前值减去前一个数值为1，则tmp++，并更新ans。可以提前判断两个值是否相等，若相等直接进入下一次循环。

发表于 2021-09-09 20:36:27 回复(0)

Java

叮叮当当的

public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        // write code here
        Arrays.sort(arr);
        int max = 1,len = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]==arr[i-1]) continue;
            if (arr[i]==arr[i-1]+1) len++;
            else len = 1;
            max = Math.max(max,len);
        }
        return max;
    }
}

发表于 2021-09-05 11:30:16 回复(1)

Java

WMYW

//手动去重+排序

import java.util.*;


public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        // write code here
        if(arr.length==1)
            return 1;
        int len;
        int res=0;
        Arrays.sort(arr);
        int i=1;
        while(i<arr.length){
            len=1;
            if(arr[i]==arr[i-1]+1){
                 while(i<arr.length&&arr[i]==arr[i-1]+1){
                     i++;
                     len++;
                     while(i<arr.length&&arr[i]==arr[i-1])
                         i++;
                 }
            }
            else
                i++;
            res=Math.max(res,len);
        }
        return res;
    }
}

发表于 2021-08-24 12:48:29 回复(0)

Java

肥嘟猫

搞不懂为什么要去重

发表于 2021-08-14 13:24:26 回复(0)

Java

我迪迦在东北

需要去重吗？排序，遇到相等的啥都不做不就行了。

import java.util.*;


public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        // write code here
        Arrays.sort(arr);
        int res = 0;
        int cnt = 1;
        for(int i=0;i<arr.length-1;i++){
            if(arr[i+1]-arr[i]==1){
                cnt++;
                if(cnt>res){
                    res = cnt;
                }
            }else if(arr[i+1]==arr[i]){
                continue;
            }else{
                cnt = 1;
            }
        }
        return res;
        
    }
}

发表于 2021-08-12 19:05:05 回复(0)

Java

Herz21

public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        // write code here
        Set<Integer> set = new HashSet<>();
        for (int t : arr) set.add(t);
        int max = Integer.MIN_VALUE;
        for (int t : arr) {
            if (set.contains(t - 1)) continue;
            int len = 1;
            while (set.contains(++t)) len++;
            max = Math.max(max, len);
        }
        return max;
    }
}

发表于 2021-07-31 10:41:28 回复(0)