숫자 배열에서 두 번째로 큰 값 찾기

숫자배열에서 두 번째로 큰 값을 찾는 몇 가지 방법을 소개한다.

 

방법 1

배열을 내림차순으로 정렬한 후, 두 번째의 값을 반환한다.

이 방법은 무척 코드로 쓰기 간단하지만, O(nlogn) 정도의 시간복잡도가 소모된다는 단점이 있다.

Arrays.sort(arr);
int second = arr[1];

 

방법 2

for문을 사용하여 순회하며 두 번째로 큰 값을 찾는 방법도 있다.

int max = -Integer.MAX_VALUE;
int second = -Integer.MAX_VALUE;

for(int i : arr) {
    if(i > max) {
        second = max;
        max = i;
    }
    else if(i > second) {
        second = i;
    }
}

 

응용으로 세 번째로 큰 값도 쉽게 구할 수 있다.

int max = -Integer.MAX_VALUE;
int second = -Integer.MAX_VALUE;
int third = -Integer.MAX_VALUE;

for(int i : arr) {
    if(i > max) {
    	third = second;
        second = max;
        max = i;
    }
    else if(i > second) {
    	third = second;
        second = i;
    }
    else if(n > third) {
    	third = n;
    }
}