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

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

程序员文章站 2022-03-01 17:18:02
...

题目描述

先给出可整合数组的定义:如果一个数组在排序之后,每相邻两个数的差的绝对值都为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(n^2)O(n2),空间复杂度为O(n)O(n)

输入描述:

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

输出描述:

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

解题思路:

1、依次考察每个子数组

2、判断每个子数组,去重后,如果最大值减去最小值,再加上1后等于元素的个数。那么这个数组就是可整合数组。

3、步骤2中符合条件的、最大的那个子数组的长度就是结果。


import java.util.Scanner;
import java.util.HashSet;
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);
    }
}