当前位置:网站首页>最长的可整合子数组的长度
最长的可整合子数组的长度
2022-07-04 18:48:00 【GreyZeng】
最长的可整合子数组的长度
作者:Grey
原文地址: 最长的可整合子数组的长度
题目链接
描述
先给出可整合数组的定义:如果一个数组在排序之后,每相邻两个数的差的绝对值都为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≤100000
,数组中每个数都满足0≤val≤10^9
要求:时间复杂度为O(n^2)
,空间复杂度为O(n)
进阶:时间复杂度O(nlogn)
,空间复杂度O(n)
暴力解法
枚举每个子数组,然后对每个子数组进行排序,然后判断是否为可整合数组,完整代码如下
public static int getLIL1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int len = 0;
// O(N^3 * log N)
for (int start = 0; start < arr.length; start++) {
for (int end = start; end < arr.length; end++) {
if (isIntegrated(arr, start, end)) {
len = Math.max(len, end - start + 1);
}
}
}
return len;
}
public static boolean isIntegrated(int[] arr, int left, int right) {
int[] newArr = Arrays.copyOfRange(arr, left, right + 1); // O(N)
Arrays.sort(newArr); // O(N*logN)
for (int i = 1; i < newArr.length; i++) {
if (newArr[i - 1] != newArr[i] - 1) {
return false;
}
}
return true;
}
暴力解法的时间复杂度是O(N^3*logN)
,显然超时。
优化解
某个数组如果属于可整合数组,则这个数组一定符合如下两个条件:
第一个条件:数组中的元素没有重复。
第二个条件:数组中的最大值和最小值的差值等于数组元素个数-1
。
如果满足上述两个条件,一定是可整合数组。
我们可以通过设置一个HashSet
来判断元素是否重复。
完整代码
public static int getLIL2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int len = 0;
int max = 0;
int min = 0;
HashSet<Integer> set = new HashSet<Integer>();
for (int l = 0; l < arr.length; l++) {
set.clear();
max = arr[l];
min = arr[l];
for (int r = l; r < arr.length; r++) {
if (set.contains(arr[r])) {
break;
}
set.add(arr[r]);
max = Math.max(max, arr[r]);
min = Math.min(min, arr[r]);
if (max - min == r - l) {
len = Math.max(len, r - l + 1);
}
}
}
return len;
}
整个算法时间复杂度O(N*logN)
,符合要求。
更多
边栏推荐
- Siemens HMI download prompts lack of panel image solution
- 15million employees are easy to manage, and the cloud native database gaussdb makes HR office more efficient
- 1011 World Cup betting (20 points) (pat a)
- HMM hidden Markov model and code implementation
- 数据集划分
- Thinking on demand development
- Integretee integrates into Moonriver through xcm, bringing enterprise class privacy solutions to its ecosystem
- 泰山OFFICE技术讲座:关于背景(底纹和高亮)的顺序问题
- [Beijing Xunwei] i.mx6ull development board porting Debian file system
- Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
猜你喜欢
C # use stopwatch to measure the running time of the program
Every time I look at the interface documents of my colleagues, I get confused and have a lot of problems...
Aiming at the "amnesia" of deep learning, scientists proposed that based on similarity weighted interleaved learning, they can board PNAS
Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
Multi table operation - external connection query
水晶光电:长安深蓝SL03的AR-HUD产品由公司供应
YOLOv5s-ShuffleNetV2
Wireshark network packet capture
What are the consequences of closing the read / write channel?
Ziguang zhanrui completed the first 5g R17 IOT NTN satellite on the Internet of things in the world
随机推荐
Ziguang zhanrui completed the first 5g R17 IOT NTN satellite on the Internet of things in the world
Development and construction of DFI ecological NFT mobile mining system
Pointnext: review pointnet through improved model training and scaling strategies++
华为nova 10系列支持应用安全检测功能 筑牢手机安全防火墙
Niuke Xiaobai month race 7 who is the divine Archer
凌云出海记 | 一零跃动&华为云:共助非洲普惠金融服务
2022 Health Exhibition, health exhibition, Beijing Great Health Exhibition and health industry exhibition were held in November
Kotlin inheritance
Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
Neural network IOT platform construction (IOT platform construction practical tutorial)
What ppt writing skills does the classic "pyramid principle" teach us?
精选综述 | 用于白内障分级/分类的机器学习技术
New wizard effect used by BCG
[QNX hypervisor 2.2 user manual]6.3.1 factory page and control page
原来这才是 BGP 协议
Detailed explanation of Audi EDI invoice message
需求开发思考
Integritee通过XCM集成至Moonriver,为其生态系统带来企业级隐私解决方案
九齐单片机NY8B062D单按键控制4种LED状态
实战模拟│JWT 登录认证