Is this a cheat? Python

  • -1

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

    Runtime: 40 ms

  • 2

    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

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

  • 0

    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)
    >>> # Sort a shuffled version of it.
    >>> random.shuffle(a)
    >>> timeit(a.sort, number=1)

Log in to reply

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