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

【搞定算法】最长的可整合子数组的长度

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

题目:最长的可整合子数组的长度。给定一个整型数组 arr,请返回其中最大可整合子数组的长度。例如:[5,5,3,2,6,4,3] 的最大可整合子数组为[5,3,2,6,4],所以返回 5。

先给出可整合数组的定义:如果一个数组在排序之后,每相邻两个数差的绝对值都为 1,则该数组为可整合数组。例如:[5,3,4,6,2] 排序之后为 [2,3,4,5,6],符合每相邻两个数差的绝对值都为 1,所以这个数组为可整合数组。

 分析:

1、暴力:

列出所有的子数组【N^2】,然后再对每个子数组复制,再排序(NlogN),再遍历看满不满足,共 O(N^3logN) 【子数组:数组中一个或连续的多个整数组成一个子数组】;

2、优化:

以后看到复杂的标准先自己改为简洁的标准。新的标准:一个数组如果是可整合的:

1)无重复值;

2)最大值减去最小值等于数组个数减 1 的话,则是可整合的。

则尝试所有的子数组的复杂度为 O(N^2),判断每个子数组是否是可整合的复杂度为 O(1)(遍历时只需要记录 min、max 就可以判断是否时可整合数组了)。

public class LongestIntegrationLength {

    public static int getLongest(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }

        int maxLen = 0;
        HashSet<Integer> set = new HashSet<>();
        // 尝试以每个 i 开头的子数组
        for(int i = 0; i < arr.length; i++){
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int j = i; j < arr.length; j++){
                if(set.contains(arr[j])){
                    // 如果包含重复数字,则直接进行一下位作为数组的开头
                    break;
                }
                set.add(arr[j]);
                max = Math.max(max, arr[j]);
                min = Math.min(min, arr[j]);
                // 数组的个数为:j - i + 1,再减去1,即为:j - i
                if(max - min == j - i){
                    // 最大减最小等于当前数组的长度,说明每个数字之间的跨度都是1,可以整合
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
            // 每次以一个新的数字作为子数组开头的时候,都要先清空set
            set.clear();
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] arr = { 5, 5, 3, 2, 6, 4, 3 };  // 5, 3, 2, 6, 4
        System.out.println(getLongest(arr));  // 5
    }
}