정렬 되 지 않 은 배열 에서 정렬 된 인접 요소 의 최대 차 이 를 계산 합 니 다.

제목.
복잡 도가 O (n) 인 알고리즘 을 설계 하여 정렬 되 지 않 은 배열 에서 정렬 한 후 인접 한 요소 의 최대 차 이 를 계산 하 십시오.정수 배열 A 와 배열 의 크기 n 을 지정 합 니 다. 최대 차 이 를 되 돌려 주 십시오.배열 요소 의 개수 가 2 보다 크 면 500 보다 작 음 을 보증 합 니 다.

    ：
[9,3,1,10],4
  ：6

해법
문 제 는 시간 복잡 도가 n 이 라 고 언급 했 기 때문에 복잡 도가 n 인 정렬 알고리즘 을 사용 해 야 합 니 다. 계산 정렬 은 좋 은 선택 입 니 다.계수 정렬 은 공간 으로 시간 을 바 꾸 는 방법 입 니 다. 먼저 정렬 되 지 않 은 배열 A [] 의 최대 값 과 최소 값 을 찾 은 다음 에 새로운 배열 arr [] 를 통 으로 만 든 다음 에 원래 배열 A [] 를 옮 겨 다 니 며 새 배열 을 A [i] - min 으로 표시 하 는 요 소 를 하나 더 해서 한 통 을 얻 습 니 다.마지막 으로 빈 통 의 개 수 를 + 1 로 계산 해 이 문제 의 답 을 얻 었 다.
아래 그림 은 통 의 상황 이다.
1
1
1
1
0
1
2
3
4
5
6
7
8
9
구체 적 인 코드 는 다음 과 같다.

import java.util.*;

public class MaxDivision {
    public int findMaxDivision(int[] A, int n) {
        // write code here
        int Max = 0,count = 0,min = A[0],max = A[0];
        for(int i = 0;i < n;i++){
            if(A[i] > max){
                max = A[i];
            }
            if(A[i] < min){
                min = A[i];
            }
        }
        //   
        int arr[] = new int[max - min + 1];
        for (int i = 0; i < A.length;i++) {
        arr[A[i] - min]++; //   
        }
        //       1
        for (int i = 0; i < arr.length;i++){
            if(arr[i] == 0){
                count++;
            }
            else{
                if(count > Max){
                    Max = count;
                }
                count = 0;
            }
        }
        return Max + 1;
    }
}