Beat 99% simple Python code with explaination


  • 0
    X

    This is just a binary search, except when you cannot find the target, you should compare target with the numbers in the narrow-down range and decide which position should be inserted.

    class Solution(object):
        def searchInsert(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            L = len(nums)
            begin = 0
            end = L - 1
            mid = (begin + end)/2
            
            b, e, m = nums[begin], nums[end], nums[mid]
            if m == target:
                return mid
            while 1:
                if end - begin <= 1:
                    if nums[begin] == target:
                        return begin
                    elif nums[end] == target:
                        return end
                    
                    # If not found, we should compare this target with elements in nums[begin:end + 1]. Note that here end - begin <= 1, so brute force search will be fine
                    if nums[begin] > target:
                        return begin
                    elif nums[end] < target:
                        return end + 1
                    else:
                        return begin + 1
                    
                if m < target:
                    begin = mid + 1
                    end = end
                elif m > target:
                    begin = begin
                    end = mid - 1
                else:
                    return mid
                mid = (begin + end)/2
                m = nums[mid]
            
    

Log in to reply
 

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