Python beats 98%


  • 14
    class Solution(object):
    def searchInsert(self, nums, key):
        if key > nums[len(nums) - 1]:
            return len(nums)
    
        if key < nums[0]:
            return 0
    
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r)/2
            if nums[m] > key:
                r = m - 1
                if r >= 0:
                    if nums[r] < key:
                        return r + 1
                else:
                    return 0
    
            elif nums[m] < key:
                l = m + 1
                if l < len(nums):
                    if nums[l] > key:
                        return l
                else:
                    return len(nums)
            else:
                return m
    

    Once the left border is larger than key, than return index. Once the right border is less than key, then return index.


  • 0
    D

    An improvement to bi-search! Thanks!


  • 0
    Z

    i have a question that is when nums[ l ] <=key ,how it works


  • 0
    D
    This post is deleted!

  • 0
    W

    I submitted your code several times but none of them beats 98%.. lol


  • 0

    It has been a while so that many faster solutions submitted. Not my fault. LoL.


  • 0
    O

    @jedihy it's only 3.47% now :P


  • 2
    S

    class Solution (object):
    def searchInsert(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    last = len (nums) - 1
    if (target < nums[0]):
    return 0
    if (target > nums[last]):
    return last + 1

        first = 0
        while first < last :
            
            mid = (first + last) / 2
            
            if (nums[mid] == target):
                return mid
            
            elif (nums[mid] > target):
                last = mid
                
            else:
                first = mid+1
                
        return first

  • 1
    D
    # code block I'm a green hand.
     def searchInsert(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            for i in nums:
                if i >= target:
                    return nums.index(i)
            return len(nums)
    

  • 2
    B
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) / 2
                if nums[mid] >= target:
                    right = mid - 1
                else:
                    left = mid + 1
    
            return left
    

  • 0
    G
    This post is deleted!

  • 0
    G

    @Blackyukun Your answer is very concise!


Log in to reply
 

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