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

楚地夏忙

看到好多人按这种思路没有去重，最后不通过的，特意写一个能通过的给大家参考。

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)

offer保命

用排序+去重不香吗（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)

JavaScript Node

♈FourBrother✅已认证♉

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)

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

牛客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

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)

猿辅导内推官

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)

duerduer冲啊

利用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)

C/C++

酣饮幻恒

利用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)

C++

等一个广哥哥

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)

wudoulieqi

排序，用map去掉重复的，找最长的连续递增子序列就可以了

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * max increasing subsequence
     * @param arr int整型vector the array
     * @return int整型
     */
    int MLS(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        map<int, int> ma;
        vector<int> a;
        for (int i = 0; i < arr.size(); i ++ ) 
        {
            if (!ma[arr[i]]) a.push_back(arr[i]); 
            ma[arr[i]] ++;
        }
        
        int num = 1, ans = 1;
        for (int i = 0; i < a.size(); i ++ )
        {
            int j = i + 1;
            if (j > a.size() - 1) break;
            if (a[i] + 1 == a[j])
            {
                num ++;
                ans = max(num, ans);
            }
            else 
            {
                num = 1;
            }
        }
        
        return ans;
    }
};

发表于 2024-05-05 10:46:06 回复(0)

Qlyer

import java.util.*;


public class Solution {
    public int MLS (int[] arr) {
        Arrays.sort(arr);
        int ans = 0;
        for (int i = 1, c = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1] + 1) {
                c++;
            } else if (arr[i] > arr[i - 1]) {
                c = 1;
            }
            ans = Math.max(ans, c);
        }
        return ans;
    }
}

发表于 2024-08-20 20:26:48 回复(0)

C++

Man9o

class Solution {
public:
    int MLS(vector<int>& v) {
        sort(v.begin(), v.end());

        int len = 1, res = 1;
        for (int i = 0; i < v.size() - 1; i++)
        {
            if (v[i] == v[i + 1] - 1) len++;
            else if (v[i] == v[i + 1]) continue;
            else len = 1;
            res = max(res, len);
        }
        return res;
    }
};

发表于 2024-07-16 16:01:50 回复(0)

C++

带着可莉去炸鱼

其实这道题如果不使用并查集直接遍历时要注意，测试用例中存在重复数值的元素，所以如果排序后不去重遍历计数时要注意对重复元素进行处理

发表于 2024-07-16 13:58:20 回复(0)

唐氏综合征

我愿称之为最简单的较难系列题，8岁李琛解法如下：

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

发表于 2024-06-14 17:08:25 回复(0)

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)

Sylvia6

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)

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)

数组中的最长连续子序列

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题