solution


  • 0
    E

    Question Description

    Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
    
    (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
    
    Find the minimum element.
    
    You may assume no duplicate exists in the array.
    

    Solutions

    Approach #1 - [Brute Force]

    status :

    • [x] AC
    • [ ] TLE

    Intuition

    Idea: what's to be said?
    find the minimum in O(n)
    

    Algorithm

    class Solution(object):
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return min(nums)
            or
            mi = max_int
            for i in xrange(len(nums)):
              mi = min(nums[i],mi)
            return mi
    

    Approach #2

    status :

    • [x] AC
    • [ ] TLE

    Intuition

    Idea: Since O(N) is quite trivial and is not what we are expecting, we can simply use binary search in this case
    
    suppose we have rotated array
    4,5,6,7,1,2,3
    
    L = 0, R = 6, mid = 3
    
    we know val[mid] > val[ed] -> minimum is in [mid+1:R]
    
    note if we have val[mid] < val[st] -> minimum is in [L:mid]
    
    in othercases, where we have val[st] <= val[mid] <= val[ed], this is a sorted array and minium is in [L:mid]
    
    

    Algorithm

    class Solution(object):
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            st,ed = 0,len(nums)-1
            while st < ed:
                mid = (st+ed)/2
                #print st,ed,mid
                if nums[mid] > nums[ed]:
                    st = mid+1
                else:
                    ed = mid
            return nums[st]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.