Is rotate nums back in sorted order an acceptable solution? Python


  • 0
    J
    class Solution(object):
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: bool
            """
            if len(nums) == 1:
                return target == nums[0]
    
            for i in xrange(0,len(nums)-1):
                if nums[i] > nums[i+1]:
                    break
                else:
                    i += 1
            return binarySearch(nums[i+1:]+nums[0:i+1],target)
    
    def binarySearch(nums,target):
        n = len(nums)
        i,j = 0,n-1
        while  i <= j :
            mid = (i+j)//2
            if target > nums[mid]:
                i = mid + 1
            elif target < nums[mid]:
                j = mid - 1
    
            else:
                return True
    
        return False
    

    Many solutions are doing complicated logic in search function, why not just rotate nums in sorted order and then find the target number? Thank you.


  • 0

    I'd say that's a bad idea. It's inefficient, and instead of the max/min point you could be searching for the target right away. Would even be a trivial and faster one-liner.


  • 0
    J

    I see, thank you.


Log in to reply
 

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