首页 > 试题广场 >

数组中的最长连续子序列

[编程题]数组中的最长连续子序列
  • 热度指数:35725 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定无序数组arr,返回其中最长的连续序列的长度(要求值连续,位置可以不连续,例如 3,4,5,6为连续的自然数)

数据范围: ,数组中的值满足
要求:空间复杂度 ,时间复杂度
示例1

输入

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

输出

4
示例2

输入

[1,1,1]

输出

1

备注:

看到好多人按这种思路没有去重,最后不通过的,特意写一个能通过的给大家参考。
class Solution {
public:
    /**
     * max increasing subsequence
     * @param arr int整型vector the array
     * @return int整型
     */
    int MLS(vector<int>& arr) {
        // write code here
        int max=0;
        sort(arr.begin(),arr.end());
        for(int i=0;i<arr.size()-1;i++)
        {
            int n=1;
            while((arr[i]+1==arr[i+1])||(arr[i]==arr[i+1]))
            {
                if(arr[i]==arr[i+1])
                {
                    i++;
                }
                else
                {
                    i++;
                    n++;
                }
            }
            if(n>max)
                max=n;
        }
        return max;
    }
};

编辑于 2020-12-04 23:22:58 回复(1)
用排序+去重不香吗(c++算法)
class Solution {
public:
    /**
     * max increasing subsequence
     * @param arr int整型vector the array
     * @return int整型
     */
    int MLS(vector<int>& arr) {
        // write code here
        sort(arr.begin(), arr.end());
        auto it=unique(arr.begin(), arr.end());
        arr.erase(it, arr.end());
        int len=1,ans=1;
        for(int i=1;i<arr.size();i++)
        {
            if(arr[i]==(arr[i-1]+1))
            {
                len++;
            }
            else
            {
                if(ans<len)
                {
                    ans=len;
                }
                len=1;
                    
            }
        }
        return max(len,ans);
    }
};

发表于 2021-03-21 22:48:53 回复(0)
import java.util.*;


public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }

        int len = arr.length;
        Arrays.sort(arr);
        int count = 1;
        int result = 1;
        for(int i=0;i<len-1;i++){
            if(arr[i+1] - arr[i] == 1){
                count++;
            }else if(arr[i+1] - arr[i] == 0){
                continue;
            }else{
                count = 1;
            }

            result = Math.max(count, result);
        }

        return result;
    }
}

发表于 2020-09-10 19:51:41 回复(2)
function MLS( arr ) {
    // write code here
    const newArr = [...new Set(arr)].sort((a, b) => a - b)
    let max = 0
    let point = -1
    let pre = Infinity
    newArr.forEach((item, index) => {
        if (point === -1) {
            max = 1
            point = 0
        } else {
            if (item === pre + 1) {
                max = Math.max(max, index - point + 1)
            } else {
                point = index
            }
        }
        pre = item
    })
    return max
}

发表于 2021-11-19 16:39:03 回复(0)
//运行时间: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)
// 换个方向,不连续的时候记录,代码会简单许多
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
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)
//手动去重+排序

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)
public class Solution {
    public int MLS (int[] arr) {
        if(arr.length == 0)
            return 0;
        int n = arr.length;
        int max = 1;
        Set<Integer> set = new HashSet<>();
        for(int num:arr)
            set.add(num);   //先将数组中的值都存储在set集合中
        for(int num:arr){
            if(set.contains(num-1)) continue;  //如果集合中包含比当前值小1的,则结束本次循环
 
            int start = num;   //不存在比当前值小1的,则去寻找以当前值开始的连续子序列
            while(set.contains(start+1)){
                start++;
            }
            //得到较长的子序列
            max = Math.max(max,start-num+1);
        }
        return max;
    }
}

发表于 2021-04-08 17:13:43 回复(0)
利用set.count查找,它返回元素在集合中出现的次数。由于set容器仅包含唯一元素,因此只能返回1或0。
class Solution {
public:
    int MLS(vector<int>& arr) {
        set<int> set;
        int max_ans = 1;
        for(int num:arr) set.insert(num);//初始化set
        for(int num:arr){
            if(set.count(num-1)) continue;//这一步不能少(否则超时),保证只从最小的数开始查
            int cnt = 1;
            while(set.count(++num)) cnt++;
            max_ans = max(max_ans,cnt);
        }
        return max_ans;
    }
};

发表于 2021-02-03 17:57:25 回复(0)
利用hash进行搜索,并且对搜索到的进行删除,复杂度O(n)。
#include <unordered_map>
class Solution {
public:
    /**
     * max increasing subsequence
     * @param arr int整型vector the array
     * @return int整型
     */
    int MLS(vector<int>& arr) {
        // write code here
        unordered_map<int, int> hash_map;
        for(int x:arr){
            hash_map[x] = 1;
        }
        int res = 0;
        for(int i = 0; i < arr.size(); i++){
            int tmp = 1;
            hash_map.erase(arr[i]);
            auto l = hash_map.find(arr[i] - 1);
            auto r = hash_map.find(arr[i] + 1);
            while(l != hash_map.end() || r != hash_map.end()){
                if(l != hash_map.end()){
                    auto tmp_i = l;
                    l = hash_map.find(l->first - 1);
                    tmp++;
                    hash_map.erase(tmp_i);
                }
                if(r != hash_map.end()){
                    auto tmp_i = r;
                    r = hash_map.find(r->first + 1);
                    tmp++;
                    hash_map.erase(tmp_i);
                }
            }
            res = max(res, tmp);
        }
        return res;
    }
};


编辑于 2020-09-05 03:39:00 回复(0)
int MLS(vector<int>& arr) {
        sort(arr.begin(),arr.end());
        vector<int> dp(arr.size(),1);
        int maxcnt = 0;
        for(int i = 1;i < arr.size();i++)
        {
            if(arr[i - 1] + 1 == arr[i])
                dp[i] = dp[i - 1] + 1;
            else if(arr[i - 1] == arr[i])
                dp[i] = dp[i - 1];
            maxcnt = max(maxcnt,dp[i]);
        }
        return maxcnt;
    }
发表于 2021-08-11 20:08:26 回复(0)
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)
public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }
 
        int len = arr.length;
        Arrays.sort(arr);
        int count = 1;
        int longestLen = 1;
        for(int i=0;i<len-1;i++){
            if(arr[i+1] - arr[i] == 1){
                count++;
            }else if(arr[i+1] - arr[i] == 0){
                continue;
            }else{
                count = 1;
            }
 
            longestLen = Math.max(count longestLen);
        }
 
        return longestLen ;
    }
}
发表于 2023-11-24 12:50:12 回复(0)
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)
class Solution {
public:
    int MLS(vector<int>& arr) {
        unordered_map<int, int> mp;
        int res = 0;
        for (int num : arr) {
            if (mp.find(num) != mp.end()) continue; // 避免重复计算
            int left = mp.find(num - 1) != mp.end() ? mp[num - 1] : 0; // 计算左边连续序列的长度
            int right = mp.find(num + 1) != mp.end() ? mp[num + 1] : 0; // 计算右边连续序列的长度
            int cur = left + right + 1; // 当前数所在的连续序列长度
            mp[num] = cur; // 将当前数及其所在的连续序列长度存入哈希表
            res = max(res, cur); // 更新最大长度
            mp[num - left] = cur; // 更新左边界所在位置的长度
            mp[num + right] = cur; // 更新右边界所在位置的长度
        }
        return res;
    }
};

发表于 2023-03-21 17:47:15 回复(0)
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def MLS(self , arr: List[int]) -> int:
        # write code here
        arr=sorted(arr)
        dp=[1]*len(arr)
        i=1
        res_l=[arr[0]]
        res=1
        while i<len(arr):
            if arr[i]==res_l[-1]+1:
                res_l.append(arr[i])
                res=max(len(res_l),res)
            elif arr[i]==res_l[-1]:
                res=max(len(res_l),res)
            else:
                res_l=[arr[i]]
            i=i+1
        return res
发表于 2023-01-09 18:04:02 回复(0)
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 length=0;
        int sum=1;
        if(arr.length==0)
        {
            return 0;
        }
        if(arr.length==1)
        {
            return 1;
        }
        for(int i=1;i<arr.length;i++)
        {
            
            if(arr[i]==(arr[i-1]+1))
            {
                sum++;
            }
            else if(arr[i]==arr[i-1])
            {
                sum=sum;
            }
            else
            {
                if(sum>length)
                {
                    length=sum;
                    
                }
                sum=1;
            }
        }
        if(sum>length)
        {
            length=sum;
        }
        return length;
    }
}
发表于 2022-07-13 10:12:35 回复(0)

标准的滑动窗口写法

class Solution:
    def MLS(self , arr: List[int]) -> int:
        N = len(arr)
        arr.sort()

        def check(l, r, rep):  # O(1) 判断是否连续
            return l < r and arr[r] - arr[l] != r - l - rep

        l, r = 0, 0
        rep = 0
        ret = 0
        while r < N:
            while check(l, r, rep):  # 当不满足时,右移 l
                if l + 1 < N and arr[l] == arr[l + 1]:
                    rep -= 1
                l += 1

            ret = max(ret, r - l + 1 - rep)
            if r + 1 < N and arr[r] == arr[r + 1]:
                rep += 1
            r += 1

        return ret
发表于 2022-03-24 12:45:44 回复(0)
***就不能给个1,2,2,2,3这样一眼能看出来的例子,还非要自己想,简单题伪装成难题是因为需要自己想案例是吧,牛客这点真的不如力扣

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