Peak Index in a Mountain Array

LeetCode 852번

Tags. binary Search

 

https://leetcode.com/problems/peak-index-in-a-mountain-array/

Peak Index in a Mountain Array - LeetCode

문제

Let's call an array A a mountain if the following properties hold:

• A.length >= 3
• There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

 

Example 1:

  Input: [0,1,0]

  Output: 1

 

Example 2:

  Input: [0,2,1,0]

  Output: 1

 

Note:

1. 3 <= A.length <= 10000
2. 0 <= A[i] <= 10^6
3. A is a mountain, as defined above.

Code

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int[] nosortA = A;
        int[] sortA = Arrays.copyOf(A, A.length);
        
        Arrays.sort(sortA);
        
        int best = sortA[sortA.length-1];
        int high = 0;
        int position = 0;
        
        int center = nosortA.length / 2;
        boolean b = true;
        while(b) {
            high = nosortA[center + position];
            if(high == best) {
                b = false;
                return center + position;
            }
            high = nosortA[center - position];
            if(high == best) {
                b = false;
                return center - position;
            }
            position++;
        }
 
        return 0;
    }
}

Solution

문제를 간단히 보자면 산이 배열로 표현이 될때 배열의 원소는 산의 높이인 것이다.

산은 중심으로 갈수록 가장 높은 고지가 높은 형태를 이루고 있으니

배열의 가장 큰 값을 찾고

배열의 중심부터 양 옆으로 큰 값을 반복해서 찾는 방향으로 코드를 작성하였다.

 

사소하지만 놓쳤던 부분인 code의 3번, 4번줄 에 있는 배열을 복사할 때 Arrays.copyOf 를 사용하지 않아 복사한 배열을 정렬했을 때 메모리 주소까지 복사당한 배열도 복사된다는 점을 기억해야한다. 

 

Runtime : 2ms

Memory : 37.9MB