[LeetCode] 153. Find Minimum in Rotated Sorted Array - Java

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Find Minimum in Rotated Sorted Array - LeetCode

---

문제

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

 

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

---

풀이

풀이 과정

주어진 nums 배열은 오름차순으로 정렬되어있는 배열을 1 ~ n 만큼 로테이션 시킨 배열이다. 로테이션 시킨다는 것은 배열의 모든 값을 한칸씩 오른쪽으로 이동시키고 초과된 마지막 인덱스 값은 처음 값으로 이동하는 것이다.

해당 배열에서 최소값을 구하여 return하는 문제이다.

먼저 최종 반환할 정답 변수를 선언하고 nums 배열의 첫 번째 값으로 초기화한다.

int answer = nums[0];

 

만약 nums 배열의 첫 번째 값이 마지막 값보다 작다면 로테이션 된 배열이 오름차순으로 정렬되어 있는 상태이므로 첫 번째 값이 최소값이 된다. 따라서 첫 번째 값을 그대로 return 한다.

*
 * 배열의 첫번째 값이 마지막 값보다 작다면
 * 오름차순으로 배열되어 있는 상태
 * -> 첫번째 값을 return
 */
if(nums[0] < nums[nums.length - 1]) return answer;

 

오름차순으로 정렬되어있지 않은 경우 두 번째 인덱스부터 마지막 인덱스까지 탐색한다.
오름차순으로 정렬된 배열을 이동시킨 것이기 때문에 현재 탐색중인 인덱스의 값이 이전 인덱스의 값보다 작아지는 경우 현재 인덱스의 값이 원래 정렬된 배열의 시작값이 된다.
오름차순으로 정렬된 배열의 시작값이 최소값이므로 정답을 갱신하고 탐색을 종료한다.

for(int i = 1; i < nums.length; i++){
    /*
     * 오름차순으로 배열된 배열을 이동시켰으므로
     * 현재 탐색값이 이전 탐색값보다 작아지는 경우
     * 현재 탐색값이 정렬된 배열의 시작값이 된다
     */
    if(nums[i] < nums[i - 1]) {
        answer = nums[i];
        break;
    }
}

 

탐색이 종료되고 구해진 정답을 최종 return 한다.

return answer;

---

 

최종 코드

class Solution {
    public int findMin(int[] nums) {
        int answer = nums[0];
        /*
         * 배열의 첫번째 값이 마지막 값보다 작다면
         * 오름차순으로 배열되어 있는 상태
         * -> 첫번째 값을 return
         */
        if(nums[0] < nums[nums.length - 1]) return answer;

        for(int i = 1; i < nums.length; i++){
            /*
             * 오름차순으로 배열된 배열을 이동시켰으므로
             * 현재 탐색값이 이전 탐색값보다 작아지는 경우
             * 현재 탐색값이 정렬된 배열의 시작값이 된다
             */
            if(nums[i] < nums[i - 1]) {
                answer = nums[i];
                break;
            }
        }

        return answer;
    }
}

---