给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）
数据范围： 
，数组中的值满足 
要求：空间复杂度 )
，时间复杂度 )
[编程题]数组中的最长连续子序列
看到好多人按这种思路没有去重，最后不通过的，特意写一个能通过的给大家参考。
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;
}
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)
排序，用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)
import java.util.*;
/**
* NC95 数组中的最长连续子序列
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public int MLS (int[] arr) {
// return solution1(arr);
// return solution2(arr);
// return solution3(arr);
// return solution4(arr);
return solution5(arr);
}
/**
* 小根堆
* @param arr
* @return
*/
private int solution1(int[] arr){
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int num: arr){
minHeap.offer(num);
}
int result = 0;
int len = 1;
int pre = minHeap.poll();
int cur;
while(!minHeap.isEmpty()){
cur = minHeap.poll();
if(cur == pre){
continue;
}
else if(cur == pre+1){
len++;
result = Math.max(result, len);
pre = cur;
}
else{
len = 1;
pre = cur;
}
}
return result;
}
/**
* 排序
* @param arr
* @return
*/
private int solution2(int[] arr){
int n = arr.length;
Arrays.sort(arr);
int result = 0;
int len = 1;
for(int i=0; i+1<n; i++){
if(arr[i+1] == arr[i]){
continue;
}
else if(arr[i+1] == arr[i]+1){
len++;
result = Math.max(result, len);
}
else{
len = 1;
}
}
return result;
}
/**
* HashSet
* @param arr
* @return
*/
private int solution3(int[] arr){
HashSet<Integer> set = new HashSet<>();
for(int num: arr){
set.add(num);
}
int result = 0;
int len;
for(int num: arr){
if(set.contains(num-1)){
continue;
}
int start = num;
len = 1;
while(set.contains(++start)){
len++;
}
result = Math.max(result, len);
}
return result;
}
/**
* HashMap
* @param arr
* @return
*/
private int solution4(int[] arr){
HashMap<Integer, Integer> map = new HashMap<>();
int result = 0;
int leftLen,rightLen,curLen;
for(int num: arr){
if(!map.containsKey(num)){
leftLen = map.getOrDefault(num-1, 0);
rightLen = map.getOrDefault(num+1, 0);
curLen = leftLen+1+rightLen;
map.put(num, curLen);
result = Math.max(result, curLen);
map.put(num-leftLen, curLen);
map.put(num+rightLen, curLen);
}
}
return result;
}
/**
* 并查集
* @param arr
* @return
*/
private int solution5(int[] arr){
UnionFind uf = new UnionFind(arr);
HashSet<Integer> set = new HashSet<>();
for(int num: arr){
set.add(num);
}
for(int num: arr){
if(set.contains(num-1)){
uf.union(num, num-1);
}
}
return uf.maxSize();
}
private class UnionFind {
int size;
HashMap<Integer, Integer> parent = new HashMap<>();
HashMap<Integer, Integer> sizeMap = new HashMap<>();
UnionFind(int[] nums){
this.size = 0;
for(int num: nums){
parent.put(num, num);
sizeMap.put(num, 1);
}
}
int find(int x){
int par = parent.get(x);
while(x != par){
parent.put(x, parent.get(par));
x = par;
par = parent.get(x);
}
return x;
}
void union(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP != rootQ){
int unionSize = sizeMap.get(rootP)+sizeMap.get(rootQ);
if(rootP < rootQ){
parent.put(rootP, rootQ);
sizeMap.put(rootQ, unionSize);
}else{
parent.put(rootQ, rootP);
sizeMap.put(rootP, unionSize);
}
this.size = Math.max(size, unionSize);
}
}
int maxSize(){
return this.size;
}
}
}
发表于 2025-02-24 13:42:43
回复(0)
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)
我愿称之为最简单的较难系列题，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)
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)
问题信息
难度：
110条回答
314收藏
7806浏览
通过挑战的用户
查看代码-
2023-02-26 11:08:58
-
2022-10-22 11:54:53 -
2022-09-18 08:03:44 -
2022-09-16 09:50:44
-
2022-09-14 14:14:23
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
