[Leetcode] 153. Find Minimum in Rotated Sorted Array

21-12-07
Sovled

Problem

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.

Solution

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l=len(nums)
        minN=nums[0]
        maxN=nums[-1]
        
        #l==1 or rotated n times
        if l==1 or minN<maxN:
            return nums[0]
        
        le=0
        ri=l-1
        
        while le<ri:
            mid=(le+ri)//2
            #print(nums[mid])
            if nums[mid]>=minN:
                le=mid+1
            else:
                ri=mid
        
        return nums[le]

배열을 두 개 적어놓고 관찰하니까, 빠르게 해답을 찾을 수 있었다. 우선 나는 n rotate한 상황을 배제해서, 정답 후보군을 항상 오른쪽에 두려고 했다. 그런 다음 바이너리 서치를 했다. 맨 왼쪽보다 더 큰 숫자이면 후보군을 mid 오른쪽으로 좁히고, 아니면 오른쪽을 mid로 후보군을 좁혔다.

if nums[mid]>=minN:

처음에 이 부분에서 등호를 넣지 않았다가, [2,1] 테스트케이스를 통과하지 못 했다.

Better Solution

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        first, last = 0, len(num) - 1
        while first < last:
            midpoint = (first + last) // 2
            if num[midpoint] > num[last]:
                first = midpoint + 1
            else:
                last = midpoint
        return num[first]

아래 부분이 내 풀이와 가장 큰 차이점이다.

if num[midpoint] > num[last]

num[last]와 num[midpoint]와 비교를 하면 된다. num[last] 내가 가진 후보군 중에서 가장 큰 숫자가 되어야한다. 반면 num[first]는 후보군 중에서 가장 작은 숫자가 되어야한다. 이러한 숫자를 찾기 위해 바이너리 서치를 돌리면 위와 같다.

며칠간 시험공부하고 와야겠다.