首页 > 试题广场 >

最长的可整合子数组的长度

[编程题]最长的可整合子数组的长度
  • 热度指数：16970 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
先给出可整合数组的定义：如果一个数组在排序之后，每相邻两个数的差的绝对值都为1，或者该数组长度为1，则该数组为可整合数组。例如，[5, 3, 4, 6, 2]排序后为[2, 3, 4, 5, 6]，符合每相邻两个数差的绝对值都为1，所以这个数组为可整合数组
给定一个数组arr, 请返回其中最大可整合子数组的长度。例如，[5, 5, 3, 2, 6, 4, 3]的最大可整合子数组为[5, 3, 2, 6, 4]，所以请返回5

数据范围：，数组中每个数都满足 

要求：时间复杂度为，空间复杂度为
进阶：时间复杂度 ，空间复杂度

注意：本题中子数组的定义是数组中连续的一段区间，例如 [1,2,3,4,5] 中 [2,3,4] 是子数组,[2,4,5] 和 [1,3] 不是子数组

输入描述:
第一行一个整数N，表示数组长度
第二行N个整数，分别表示数组内的元素


输出描述:
输出一个整数，表示最大可整合子数组的长度
示例1

输入

7
5 5 3 2 6 4 3

输出

5
示例2

输入

3
1 4 2

输出

1
算法知识视频讲解
添加回答
becatjd头像 becatjd 
import java.util.*;
public class Main{
    public static void main(String[] args){
        //思路：可整合数组满足：最大值-最小值+1=长度
        //两边遍历，对每一个子数组进行判断
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<arr.length;i++){
            arr[i] = sc.nextInt();
        }
        ArrayList<Integer> length = new ArrayList<>();//存放可整合子串的长度
        length.add(1);
        for(int i=0;i<arr.length;i++){
            int max = arr[i];
            int min = arr[i];
            for(int j=i+1;j<arr.length;j++){
                max = Math.max(max,arr[j]);
                min = Math.min(min,arr[j]);//从arr[i]到arr[j]，找到最大值和最小值
                if(max-min==j-i){//如果最大值-最小值+1=j-i+1，则是可整合数组
                    length.add(max-min+1);
                }
            }
        }
        Collections.sort(length);//升序
        Collections.reverse(length);//逆序
        System.out.println(length.get(0));//输出最大长度
    }
}

发表于 2020-04-05 20:22:58 回复(0)
元暗头像 元暗
代码如下的 
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int N = scanner.nextInt();

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }
        HashSet<Integer> set = new HashSet<>();
        int maxCount = 1;
        for (int i = 0; i < N; i++) {
            if (maxCount >= N - i + 1) {//剩下的数组所最大可整合已不可能超过现在的数组，则直接跳出
                break;
            }
            int max = arr[i], min = arr[i];
            set.add(arr[i]);
            for (int j = i + 1; j < N; j++) {
                if (set.contains(arr[j])) {
                    break;
                }
                set.add(arr[j]);
                if (arr[j] > max) {
                    max = arr[j];
                }
                if (arr[j] < min) {
                    min = arr[j];
                }
                if (max - min == j - i) {//如果当前数组没有重复，而且最大值减去最小值等于数组长度-1，那么当前数据就是可整合数组
                    maxCount = max - min + 1 > maxCount ? max - min + 1 : maxCount;
                }
            }
            set.clear();
        }
        System.out.println(maxCount);
    }
}


发表于 2019-08-04 11:05:09 回复(4)
fangqi_方其头像 fangqi_方其 
import java.util.*;

public class Main {

    public static void main(String[] arg) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int[] dp = new int[n];
        dp[0] = 1;
        Integer ans = 1;
        for (int i = 1; i < n; i++){
            if (arr[i] - arr[i-1] == 1){
                dp[i] = dp[i - 1] + 1;
            }else if (arr[i] == arr[i-1]){
                dp[i] = dp[i-1];
            }else{
                dp[i] = 1;
            }
            ans = Math.max(ans,dp[i]);
        }
        System.out.println(ans);

    }


}
编辑于 2019-09-19 10:39:13 回复(2)
谜摆头像 谜摆 
#include <algorithm>
#include <vector>
#include <unordered_set>
using namespace std;
#define INT_MIN     (-2147483647 - 1) // minimum (signed) int value
#define INT_MAX       2147483647    // maximum (signed) int value

//解法：套路定理：若一段无重复的数中，最大值减去最小值+1等于该数组长度，则数组可整合。
int main()
{
	int n;
	scanf("%d", &n);
	if (n <= 0)
	{
		printf("0");
		return 0;
	}
	else if (n == 1)
	{
		printf("1");
		return 0;
	}

	vector<int> vec(n);
	for (int i = 0; i < n; i++)scanf("%d", &vec[i]);
	unordered_set<int> set;
	int res = 1;
	for (int i = 0; i < n; i++)
	{
		int min = INT_MAX, max = INT_MIN;
		for (int j = i; j < n; j++)
		{
			if (set.find(vec[j]) != set.end())break;
			set.insert(vec[j]);
			if (vec[j] < min)min = vec[j];
			if (vec[j] > max)max = vec[j];
			if (max - min == j - i)res = res < j - i + 1 ? j - i + 1 : res;
		}
		set.clear();
	}
	printf("%d", res);
}

发表于 2019-08-10 01:17:42 回复(0)
小星教授头像 小星教授 
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        
        Set<Integer> set = new HashSet<>();
        int len = 1;
        for(int i=0;i<n;i++){
            int max = arr[i];
            int min = arr[i];
            for(int j=i;j<n;j++){
                if(set.contains(arr[j])){
                    break;
                }else{
                    set.add(arr[j]);
                }
                max = Math.max(arr[j],max);
                min = Math.min(arr[j],min);
                if(max-min+1 == set.size()){
                    len = Math.max(len,max-min+1);
                }
            }
            
            set.clear();
        }
		System.out.print(len);
		
	}
}

发表于 2019-10-21 16:48:01 回复(0)
chyelang头像 chyelang
动态规划，先排序
N = int(input())
arr = list(map(int, input().split(" ")))
arr.sort()
ret = [1 for i in range(len(arr))]
for i in range(1, len(arr)):
    if arr[i] == arr[i-1]:
        ret[i] = ret[i-1]
    elif arr[i] - arr[i-1] == 1:
        ret[i] = ret[i-1] + 1
print(max(ret))


发表于 2020-01-26 18:10:58 回复(4)
Java
牛客566750720号头像 牛客566750720号 

import java.util.Scanner;
//可整合数的长度确认，时间复杂都n^3 没排序
public class IntegrateArr {
	public static void main(String[] args) {
		
		//设置间隔和arr的大小
		int interval = 1, N;
		
		Scanner x = new Scanner(System.in);
		N = x.nextInt();
		
		int[] arr = new int[N];
		//定义一个保存记录可整合数长度的数组
		int[] count = new int[N];
		
		for(int i= 0; i<N; i++) {
			arr[i] = x.nextInt();
			count[i] = 1;	//初始化记录可整合数
		}
		
		//定义临时比较操作数
		int temp;
		for(int i = 0;i<arr.length;i++) {
			temp = arr[i];
			for(int j=0 ;j < arr.length; j++) {
				if(temp - arr[j] == interval) {					
					count[i]++;					
					temp = arr[j];
					j = -1;//重头循环找下一个
				}			
			}			
		}
		//取最大保存的可整合数长度的数组的记录
		int max = count[0];
		for(int i = 1 ;i<count.length; i++) {
			if(count[i]>max) {
				max = count[i];
			}
		}
		//输出长度
		System.out.println(max);		
	}
}


发表于 2019-12-08 20:30:39 回复(0)
Java
Mono_Chrome头像 Mono_Chrome 
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static int getMaxLIL(int[] arr) {

        HashSet<Integer> set = new HashSet<>();
        int len = 0;

        for (int i = 0; i < arr.length; i++) {
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;

            for (int j = i; j < arr.length; j++) {
                if (set.contains(arr[j])) {
                    break;
                }
                set.add(arr[j]);
                max = Math.max(max, arr[j]);
                min = Math.min(min, arr[j]);
                if (max - min == j - i) {
                    len = Math.max(len, j - i + 1);
                }
            }
            set.clear();
        }
        return len;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(getMaxLIL(arr));
    }

}
发表于 2019-10-11 15:30:27 回复(0)
签约顺利万事大吉头像 签约顺利万事大吉
/*
    时间:nlogn
    方法:排序后 dp
*/ 
#include<iostream>
#include<algorithm>
using namespace std;
int nums[5005];
int dp[5005];
int ans=0;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>nums[i];
    sort(nums,nums+n,less<int>());
    dp[0]=1;
    for(int i=1;i<n;i++){
        if(nums[i]-nums[i-1]==1) dp[i]=dp[i-1]+1;
        if(nums[i]==nums[i-1]) dp[i]=dp[i-1];
        else dp[i]=1;
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

发表于 2019-08-20 15:49:39 回复(2)
Python
圣诞节的安徒生头像 圣诞节的安徒生
感觉子数组的问题还没有考虑完全 
n = eval(input())
ls = list(map(int, input().split()))
ls.sort()
i = 1
count = 1
if len(ls) == 1 or len(ls) == 0:
    print(len(ls))
while i < len(ls):
    if ls[i]-ls[i-1] == 1:
        count += 1
        i += 1
    else:
        i += 1
print(count)
遍历子数组，却超时！ 
#接收用户输入
N = eval(input())
#接收空格输入整型数组
ls = list(map(int, input().split()))
#最大可整合子数组的长度初始化为0
res_length = 0
while len(ls) > res_length: # 循环遍历子数组
    for i in range(len(ls)):
        tmp = ls[:i+1]
        tmp.sort()
        # 排序后首尾相减加一若等于长度，则可整合
        if tmp[-1]-tmp[0]+1 == len(tmp) and len(tmp)>res_length:
            res_length = len(tmp)
    ls = ls[1:] #每次数组调整为去除第一位元素的新数组
print(res_length)



编辑于 2019-08-12 11:13:48 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    if(n<=1)
        cout<<n<<endl;
    else{
        int a[n], cnt=1;
        for(int i=0;i<n;i++)
            cin>>a[i];
        unordered_set<int> S;
        for(int i=0;i<n;i++){
            int Max = 0, Min = INT_MAX;
            for(int j=i;j<n;j++){
                if(S.find(a[j])!=S.end())
                    break;
                S.insert(a[j]);
                Min = min(Min, a[j]);
                Max = max(Max, a[j]);
                if(Max-Min==j-i)
                    cnt = max(cnt, j-i+1);
            }
            S.clear();
        }
        cout<<cnt<<endl;
    }    
    return 0;
}

发表于 2020-01-27 01:20:50 回复(0)
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,ans=1;
    cin>>n;
    if(n==0)
    {
        cout<<0<<endl;
        return 0;
    }
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
    sort(num.begin(),num.end());
    for(int i=1; i<n; ++i)
        if(num[i]-num[i-1]==1)
            ans++;
    cout<<ans<<endl;
    return 0;
}

发表于 2019-08-22 22:43:46 回复(0)
C++
福哥儿头像 福哥儿 
// use vector.assign to truncate array
int maxlen(vector array)
{
    if (array.size() <= 1) return array.size();
    vector arr;
    int max = 1, ret = 1;
    for (int i = 0; i < array.size(); i++) {
        for (int j = i + 1; i < array.size(); i++) {
            // sub array
            arr.assign(array.begin() + i, array.begin() + j);
            // sort
            sort(arr.begin(), arr.end());
            // remove duplicate
            arr.erase(unique(arr.begin(), arr.end()), arr.end());
            // calculate max len
            max = 1;
            for (int i = 1; i < arr.size(); i++) {
                if (arr[i] == arr[i - 1] + 1) {
                    max++;
                } else {
                    ret = max(max, ret);
                    max = 1;
                }
            }
            ret = max(max, ret);
        }
        arr.clear();
    }
    return ret;
}
发表于 2022-11-04 02:39:43 回复(0)
牛客235394036号头像 牛客235394036号
暂时还没想到O(NlogN)的解法，有大佬踢我一下
主要就是评论里各位提的判断是否重复的方法 
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int []arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        int res = maxSubArray(arr, N);
        System.out.println(res);
    }

    private static int maxSubArray(int []arr, int n) {
        HashSet<Integer> set = new HashSet<>();
        int res = 1;
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
            int max = arr[i];
            int min = arr[i];
            int temp = 0;
            for (int j = i + 1; j < arr.length; j++) {
                if (set.contains(arr[j])) break;
                if (max < arr[j]) max = arr[j];
                if (min > arr[j]) min = arr[j];
                if (max - min == j - i) temp = max - min + 1;
                }
            res = Math.max(res, temp);
            set.clear();
            }
            return res;
        }
}


发表于 2022-05-23 18:28:46 回复(0)
牛娃牛娃头像 牛娃牛娃 
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    if(n==0){
        cout<<0<<endl;
        return 0;
    }
    vector<int> num(n);
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    //先对输入的数组排序
    sort(num.begin(),num.end());
    vector<int> dp(n);
    dp[0]=1;
    int res =1;
    for(int i=1;i<n;i++){
        if(num[i]-num[i-1]==1){
            dp[i]=dp[i-1]+1;
        }else if(num[i]==num[i-1]){
            dp[i]=dp[i-1];
        }else{
            dp[i]=1;
        }
        res =max(res,dp[i]);
    }
    cout<<res<<endl;
    return 0;
    
}
不知道为什么  5    1 9 2 10 3 这个输出为啥 是1  排序后不应该是 123910 最长的不应该是123吗。。。
发表于 2022-05-22 16:02:10 回复(0)
Lothakim头像 Lothakim
这***题，明明说的子数组，nmd排行前几的答案全是按子序列写的，这也能过，这题真的纯纯的脑瘫
发表于 2022-04-20 16:56:42 回复(0)
C++
牛客423041527号头像 牛客423041527号 
/*可以找数组最大值和最小值，如果最大值和最小值之差就是数组长度就说明是可整合数组*/
#include<iostream>
#include<vector>
using namespace std;
bool integrable2(long long a[],int pos0,int pos1)//数组，起始位置，终止位置 
{
	long long minn=1000000000;
	long long maxx=0; 
	for(int i=pos0;i<pos1+1;i++)
	{
		if(a[i]>maxx) maxx=a[i];
		if(a[i]<minn) minn=a[i];
        for(int j=i+1;j<pos1+1;j++)
		{
			if(a[i]==a[j]) return false;
		}
	}
//	cout<<"p0:"<<pos0<<"p1:"<<pos1<<"max:"<<maxx<<"min:"<<minn<<endl;
	if(maxx-minn==pos1-pos0) return true;
	else return false;

 } 
// bool integrable(long long a[],int pos0,int pos1)//数组，起始位置，终止位置 
// {
// 	int temp;
// 	for(int i=1;i<pos1-pos0+1;i++)//冒泡趟数 
// 	{
// 		for(int j=pos0;j<pos1+1-i;j++)//坐标 
// 		{
// 			if(a[j]>a[j+1])
// 			{
// 				temp=a[j];a[j]=a[j+1];a[j+1]=temp;
// 			}
// 		}
// 	}
// //	for(int i=pos0;i<pos1+1;i++)
// //	{
// //		cout<<a[i]<<" ";
// //	}
// //	cout<<endl;
// 	for(int i=pos0;i<pos1;i++)
// 	{
// 		if(a[i+1]-a[i]!=1) return false;
// 	}
// 	return true;
//  } 
int main()
{
	long long a[1000000];
	int n;
	int maxx=0; 
	vector<int>dp(100,1);
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];		
	}
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(integrable2(a,j,i))//是可整合数组 
			{
				dp[i]=max(dp[i],i-j+1);				
			}
		}
	}
	for(int i=0;i<n;i++) 
	{
//		cout<<dp[i]<<" ";
		if(dp[i]>maxx)
		maxx=dp[i];
	}
	cout<<maxx<<endl;
} 
无论如何都会超时，人已经麻了
发表于 2022-04-17 12:45:43 回复(0)
Python 3
牛客989469880号头像 牛客989469880号
n=eval(input())
t=list(map(eval,input().split()))
num=0
for i in range(len(t)):
    a=[]
    for j in range(len(t)-1,i,-1):
        a=t[i:j+1]
        b=list(set(a))
        if len(b)!=len(a):
            continue
        if len(a)<num:
            break
        if b[-1]-b[0]==len(b)-1:
            if len(b)>num:
                num=len(b)
                break
print(num)
一直超时，有什么好的办法吗？
发表于 2022-04-10 11:31:31 回复(0)
六七八头像 六七八 
package main

import (
	"fmt"
	"math"
)

func main() {
    var n int
    fmt.Scan(&n)
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&arr[i])
    }
	res := 0
	for i := 0; i < len(arr); i++ {
		m := make(map[int]int)
		min, max := math.MaxInt32, math.MinInt32
		for j := i; j < len(arr); j++ {
			if m[arr[j]] > 0 {
				break
			}
			m[arr[j]]++
			if arr[j] < min {
				min = arr[j]
			}
			if arr[j] > max {
				max = arr[j]
			}
			if max-min == j-i && j-i+1 > res {
				res = j - i + 1
			}
		}
	}
	fmt.Println(res)
}

发表于 2022-03-11 15:44:48 回复(0)
C++
麦芒2021头像 麦芒2021
思路：
判断f[i][j]是否满足要求
判断方法是，用哈希表判断是否又重复元素，如果没有重复元素，判断是否下标差等于最大最小差 
#include "iostream"
#include "vector"
#include "unordered_set"
#include "limits.h"//INT_MIN定义
#include "algorithm"
#include <cmath>//INT_MAX
//#include "bits/stdc++.h"

using namespace std;
int main()
{
    int len;
    cin>>len;
    vector<int> vec(len);
    for(int i=0;i<len;i++)
    {cin>>vec[i];}
    int ret=1;
    for(int i=0;i<len;i++)
    {
        unordered_set<int> ump;
        int max_num=0,min_num=INT_MAX;
        for(int j=i;j<len;j++)
        {
            if(ump.count(vec[j])==1) break;
            max_num=max(max_num,vec[j]);
            min_num=min(min_num,vec[j]);
            if(j-i==max_num-min_num)
            {
                ret=max(ret,j-i+1);
            }
        }
    }
    cout<<ret;
    return 0;
}


发表于 2021-12-26 11:26:14 回复(0)
提交观点

问题信息

动态规划 模拟
上传者：小小
难度：
64条回答 9196浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号