[LeetCode] 153. Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array - LeetCode

 

오름차순으로 정렬된 길이 n의 배열이 1에서 n회 사이로 회전한다고 가정합니다.

정렬된 회전 배열의 고유 원소의 개수가 주어지면, 이 배열의 최소 원소를 반환합니다.

 

O(log n) 시간 내에 실행되는 알고리즘을 작성해야 합니다.

 

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.

 

문제접근

O(log n) 시간 내에 실행되는 알고리즘을 작성해야 합니다.

이번에도 이분탐색을 생각했습니다.

 

하지만 배열이 정렬되지 않았기 때문에 아이디어가 필요해 보였습니다.가장 작은값을 찾는 문제이기때문에 이분탐색을 할때마다 작은값을 찾았습니다.

    public int findMin(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n-1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (mid < n-1 && nums[mid] > nums[mid + 1]) {
                left = mid + 1;
            } else if (mid > 1  && nums[mid] > nums[mid - 1]) {
                right = mid - 1;
            } else {
                return nums[left];
            }
        }
        return nums[left];
    }

하지만 이 코드는 처음 설정되는 mid값이 가장 작은값이라면 정답을 찾지 못합니다.

 

다른사람의 코드

 

우선 min값을 구하기위한 변수를 선언하고 이분탐색을 할때마다 mid값과 비교하여 최소값을 저장합니다.

 

그리고 가장 작은쪽은 선택하기 위해 left가 right보다 작고, left가 mid보다 작다면

왼쪽에 있는 곳이 작은 요소가 있는 쪽이니 right를 mid -1합니다.

 

그게 아니라면 left를mid +1을하여 최소값을 찾는 코드입니다.   

public int findMin(int[] nums) {
        int min = Integer.MAX_VALUE;;
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while (l <= r) {
            int m = (l + r)/ 2;
            min = Math.min(nums[m], min);

            if (nums[l] < nums[r] && nums[l] < nums[m]) {
                r = m - 1;
            } else{
                l = l + 1;
            }
        }
        return min;
    }

시간복잡도

이분탐색을통해 O(log n)의 시간복잡도를 갖고있습니다.

 

느낀점

정렬되어있지 않은 배열을 이분탐색하는것은 정말 어려운것 같습니다...

문제를 잘 정의하고 파악해서 접근해야겠다는 생각이 들었습니다.

 

참고

Using Binary Search - Find Minimum in Rotated Sorted Array - LeetCode