Is this a cheat? Python


  • -1
    Z

    class Solution(object):
    def findMin(self, nums):
    nums.sort()
    return nums[0]

    Runtime: 40 ms


  • 2
    I

    It's too slow if you sort. For the case without duplicate numbers, time complexity for this problem is only O(lgn) while sorting's time complexity is O(nlgn).


  • 0
    L

    yes, you are right. I consider the array as a heap, it's O(logn)


  • 0
    W

    The problem is supposed to be solved by Binary Search, O(lg(n)) time would be used.
    Using return min(nums) is the simplest in Python. However, it is very slow.


  • 0

    Sorting only takes O(n) here. Demo:

    >>> import random
    >>> from timeit import timeit
    
    >>> # Sort a rotated sorted list.    
    >>> a = range(3333333, 10000000) + range(3333333)
    >>> timeit(a.sort, number=1)
    0.11482411267604675
    
    >>> # Sort a shuffled version of it.
    >>> random.shuffle(a)
    >>> timeit(a.sort, number=1)
    6.308021483568041

Log in to reply
 

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