Python solution. Worst case O(N)


  • 6
    A
    def findMin(self, nums):
        beg = 0
        end = len(nums)-1
        while beg <= end:
            while beg < end and nums[beg] == nums[beg + 1]:
                beg += 1
            while end > beg and nums[end] == nums[end - 1]:
                end -= 1
            if beg == end:
                return nums[beg]
            
            mid = (beg+end)/2
            if nums[mid] > nums[end]:
                beg = mid + 1
            else:
                end = mid
            
                
        return nums[beg]

  • 0
    def findMin(self, nums):
            l, r = 0, len(nums) - 1
            while l < r:
                m = (l + r) >> 1
                if nums[m] > nums[r]:
                    l = m + 1
                elif nums[m] < nums[r]:
                    r = m
                else:
                    r = r - 1
            return nums[l]

Log in to reply
 

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