[알고리즘] 가장 긴 통합 가능 한 배열 의 길이

제목:
만약 한 배열 이 다시 정렬 한 후에 인접 한 두 개의 수차 의 절대 값 이 모두 1 이 라면 이 배열 은 통합 가능 한 배열 이다.예 를 들 어 [5, 3, 4, 6, 2] 순 서 를 매 긴 후에 [2, 3, 4, 5, 6] 이 고 인접 한 두 수의 차 에 부합 되 는 절대 치 는 1 이기 때문에 이 배열 은 통합 가능 한 배열 이다.
전체 배열 을 지정 하 였 습 니 다. 하위 배열 을 통합 할 수 있 는 최대 길 이 를 되 돌려 주 십시오.예 를 들 어 [5, 5, 3, 2, 6, 4, 3] 의 최대 통합 가능 한 서브 배열 은 [5, 3, 2, 6, 4] 이 므 로 5 로 돌아간다.
방법 1:
1. 각 하위 배열 의 arr [i... j] 를 차례대로 살 펴 보면 모두 O (N ^ 2) 개가 있다.
2. 모든 하위 배열 에 대해 새로운 배열 로 복사 하고 new Arr 로 기록 한 다음 new Arr 를 정렬 한 다음 통합 가능 한 배열 의 정의 에 부합 되 는 지 검증 합 니 다. 이 단계 의 대 가 는 O (NLogN) 입 니 다.
3. 단계 2 에서 조건 에 부합 되 고 가장 큰 하위 배열 의 길이 가 결과 이다.
시간 복잡 도: O (N ^ 3logN)

public static int getLIL1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int len = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (isIntegrated(arr, i, j)) {
                    len = Math.max(len, j - i + 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;
    }

방법 2:
첫 번 째 방법 은 제목 의 뜻 에 따라 모든 하위 배열 이 통합 가능 한 배열 인지 엄 격 히 검증 하지만 배열 이 통합 가능 한 배열 인지 아 닌 지 를 판단 하 는 데 다음 과 같은 방법 으로 판단 할 수 있다. 한 배열 에 중복 요소 가 없 으 면 최대 치 에서 최소 치 를 빼 면 1 의 결 과 는 요소 의 개수 (max - min + 1 = 요소 개수) 와 같다.그럼 이 배열 은 통합 가능 한 배열 입 니 다.
이렇게 해서 하나의 배열 이 배열 을 통합 할 수 있 는 시간 복잡 도 인지 검증 하면 첫 번 째 방법의 O (NLogN) 에서 O (1) 로 줄 일 수 있 고 전체 과정의 시간 복잡 도 는 O (N ^ 2) 이다.

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<>(); //    
        for (int i = 0; i < arr.length; i++) {
            max = Integer.MIN_VALUE;
            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]);
                if (max - min == j - i) {
                    len = Math.max(len, j - i + 1);
                }
            }
            set.clear();
        }
        return len;
    }