Simple Python recursion method 40ms


  • 1
    4
    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def findMin(self, nums):
            l = len(nums) - 1
            if l <= 1:
                return min(nums)
            mid = l / 2
            if nums[0] < nums[mid]:
                return self.findMin([nums[0]] + nums[mid+1:])
            else:
                return self.findMin(nums[1:mid+1])

  • 1
    D

    As far as I can remember, slice k elements out of a list takes O(k) time. So it is a O(n) solution. Better to pass array index into your function


  • 0
    C

    Yes, normally it should be better to pass indexes rather than array slices:

    # Recursively 
    def findMin(self, nums):
        return self.helper(nums, 0, len(nums)-1)
            
    def helper(self, nums, l, r):
        if l == r:
            return nums[l]
        mid = l + (r-l)//2
        if nums[mid] > nums[r]:
            return self.helper(nums, mid+1, r)
        else:
            return self.helper(nums, l, mid)
    

  • 0
    S

    I think you only consider the situation that the original list is ascending. If the test case is [2, 1,7,6,5,4], it will return 4 not 1. I think the question should specify that the original list is ascending.


Log in to reply
 

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