首页 > 试题广场 >

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

[编程题]最长的可整合子数组的长度

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

数据范围： $0 < n \le 100000$ ，数组中每个数都满足 $0 \le val \le 10^9$

要求：时间复杂度为 $O(n^2)$ ，空间复杂度为

进阶：时间复杂度 $O(nlogn)$ ，空间复杂度 $O(n)$

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

输入描述:

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

输出描述:

输出一个整数，表示最大可整合子数组的长度

示例1

输入

7
5 5 3 2 6 4 3

输出

示例2

输入

3
1 4 2

输出

算法知识视频讲解

哈哈～柳暗花明

发表于 2020-07-21 13:15:20

感觉题目有点歧义，子数组可以不连续，所以有重复数据也可以去重排序后计算1、731 ms 4088K def check(l): return len(l) == (l[-1] - l[0] + 1) while True: try: n = int(input 展开全文

夜行斑马

发表于 2020-11-13 17:02:05

使用语言：C++时间复杂度：空间复杂度：解题思路：可以先从数组的性质下手，对于一个排好序的数组，如果要让数组中每个相邻元素的差都为1，那么数组的长度一定会等于数组中最大值与最小值的差值。反过来推导，如果数组的长度等于数组中最大值与最小值的差值，就只有两种情况：1、数组中存在相等的元素，比如：[2 展开全文

罗毅lala

发表于 2020-03-11 20:06:46

#include<iostream> #include<vector> #include<algorithm> #include<unordered_set> using namespace std; //1，将数组用哈希表存储起来这样可以实现快速查展开全文

快支棱起来的椰子很愤怒

发表于 2022-01-07 15:28:39

// python3 无法通过 package main import ( "fmt" "math" ) func max(x, y int) int { if x > y { return x } return y } fu 展开全文

牛客515241338号

发表于 2022-05-23 17:30:29

let num = parseInt(readline()); let str = readline().split(" ").map(Number); let arr = [], s = 0, count = 0; str.sort((a, b) => a - b); for (let i 展开全文

无语的花生米复盘中

发表于 2022-03-05 21:27:51

package main //输入描述： //第一行一个整数N，表示数组长度 //第二行N个整数，分别表示数组内的元素 //输出描述： //输出一个整数，表示最大可整合子数组的长度 import ( "bufio" "fmt" "os" "strconv" "strings" ) fu 展开全文

灌江口小二郎

发表于 2021-09-22 10:48:57

这个题有歧义，测试用例也不友好 #include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; int main() { 展开全文

lxh666

发表于 2022-04-21 19:24:47

public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=Integer.parseInt(sc.nextLine() 展开全文

喜欢编程滑雪乒乓球篮球

发表于 2021-11-20 16:09:33

核心思想：当数组中无重复元素时，如果数组中最大值-最小值= 数组的长度-1，则此时子数组符合题意，我们只需要找出最大长度即可 package main import ( "fmt" ) func max(x, y int) int { if x > y { 展开全文

问题信息

动态规划模拟

上传者：小小

难度：

64条回答 91收藏 10089浏览

通过挑战的用户

查看代码

Andy9898

2023-03-05 13:26:05
剑胆琴心_liu

2022-11-11 21:08:06
瓜皮秀才

2022-10-23 21:00:54
牛客54758...

2022-09-16 17:17:07
牛客54349...

2022-09-13 11:08:02

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

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题