Divided and conquer method


  • 0
    W
    # worst case o(n) complexity
    
        class Solution:
            # @param {integer[]} nums
            # @return {integer}
            def findMin(self, nums):
                if not nums:
                    return None
                if len(nums)==1:
                    return nums[0]
                i = 0
                j = len(nums)-1
                if nums[0] != nums[-1]:
                    while i < j :
                        k = (i+j)//2
                        if nums[k] <= nums[j]:
                            j = k
                        else:
                            i = i+1
                    return nums[i]
                else:
                    k = len(nums)//2
                    left = self.findMin(nums[:k])
                    right = self.findMin(nums[k:])
                    return min(left, right)

Log in to reply
 

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