Daily Algorithm - Find Minimum in Rotated Sorted Array

Description

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.

Accepted

1.4M

Submissions

2.8M

Acceptance Rate

Solution

• 이 문제에서 하나의 사실은 왼쪽 인덱스 값이 오른쪽 인덱스 값보다 크면 해당 배열은 정렬된 것이므로 제일 왼쪽 인덱스의 값이 가장 작은 값이라는 사실이다.

• 첫번째 풀이는 최악의 경우 O(n)의 시간복잡도를 가질 수 있는 풀이이다. 왼쪽과 오른쪽 중 어느쪽이 더 작은지만을 비교해 작은 쪽에서 차례로 가장 작은 값을 찾는 풀이이기 때문이다. 따라서 O(log n)의 풀이에는 맞지 않다.

class Solution {
    fun findMin(nums: IntArray): Int {
        if (nums.size == 1) return nums[0]
        var l = 0
        var r = nums.lastIndex
        var min = 0
        if (nums[l] < nums[r]) {
            min = nums[l]
        } else {
            min = nums[r]
            while (nums[r-1] < nums[r]) {
                min = nums[r-1]
                r--
            }
        }
        return min
    }
}

• 두번째 풀이는 이진 탐색을 이용한 풀이이다.
• 왼쪽과 오른쪽중 가장 작은 값이 있을 부분을 찾아서 이진탐색으로 가장 작은 값을 찾아나가는 풀이이다.
• 우선 가운데 값이 왼쪽보다 크다면 가장 작은 값은 오른쪽에 있으며, 가운데 값이 왼쪽보다 작다면 가장 작은 값은 왼쪽 부분에 속해있다.
• 따라서 왼쪽 값을 가운데 값과 비교하며 l과 r 인덱스를 옮겨가면 된다.
• 또 하나의 포인트는 가장 작은 값을 res 변수에 저장해, l과 r을 옮겨서 구한 m 인덱스의 값을 비교하면서 가장 작은 값을 찾는 것이다.
• 이렇게 해야 m 인덱스 값이 최소값일 경우를 빠지지 않고 체크할 수 있다.

class Solution {
    fun findMin(nums: IntArray): Int {
        var l = 0
        var r = nums.lastIndex
        var m = (l + r) / 2
        var res = nums[m]
        
        while (l <= r) {
            if (nums[l] <= nums[r]){ 
                res = Math.min(res, nums[l])
                break
            }
            
            if (nums[l] <= nums[m]) {
               l = m + 1
            } else {
               r = m - 1
            }
            m = (l + r) / 2
            res = Math.min(res, nums[m])
        }
        
        return res
    }
}