最长的可整合子数组的长度
程序员文章站
2022-03-01 17:17:32
...
题目描述
先给出可整合数组的定义:如果一个数组在排序之后,每相邻两个数的差的绝对值都为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。
[要求]
时间复杂度为,空间复杂度为
输入描述:
第一行一个整数N,表示数组长度
第二行N个整数,分别表示数组内的元素
输出描述:
输出一个整数,表示最大可整合子数组的长度
示例1
输入
7 5 5 3 2 6 4 3
输出
5
解法:
注意,题干说的是“子数组”,很多排序后扫描一遍的做法虽然能过,但是方法与题意是不符的,大概是因为数据弱的原因。
回到题目上来,假设一个数组是可整合的数组,那么它应该满足以下两个条件:
1:没有重复元素;
2:最大值与最小值之差加一等于数组长度。
鉴于上述两个特征,我们可以遍历所有可能的子数组,找到最大值。
代码:
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
int main(void) {
int n;
scanf("%d", &n);
vector<int> a(n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
// unordered_set基于哈希表实现
unordered_set<int> _hash;
int mn, mx;
int ret = 1;
for (int i = 0, j; i < n; ++i) {
//优化,如果最大长度大于剩下的元素个数,直接终止循环
if (ret > n - i) break;
mn = mx = a[i];
for (j = i; j < n; ++j) {
if (_hash.count(a[j])) break;
_hash.insert(a[j]);
mn = min(mn, a[j]);
mx = max(mx, a[j]);
if (mx - mn == j - i) ret = max(ret, j - i + 1);
}
_hash.clear();
}
printf("%d\n", ret);
return 0;
}
上一篇: 最长的可整合子数组的长度
下一篇: linux集群分发脚本