欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 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。

[要求]

时间复杂度为O(n2)O(n^2),空间复杂度为O(n)O(n)

输入描述:
第一行一个整数N,表示数组长度
第二行N个整数,分别表示数组内的元素
输出描述:
输出一个整数,表示最大可整合子数组的长度
示例1
输入
7 5 5 3 2 6 4 3
输出
5
解法:

注意,题干说的是“子数组”,很多排序后O(n)O(n)扫描一遍的做法虽然能过,但是方法与题意是不符的,大概是因为数据弱的原因。

回到题目上来,假设一个数组是可整合的数组,那么它应该满足以下两个条件:

1:没有重复元素;

2:最大值与最小值之差加一等于数组长度。

鉴于上述两个特征,我们可以遍历所有可能的子数组O(n2)O(n^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;
}