035.md

35. Search Insert Position

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/search-insert-position/description/

内容描述

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0

解题方案

思路 1 - 时间复杂度: O(N) - 空间复杂度: O(1)

beats 10.59%

找到第一个比target大的值的index，如果没找到则返回len(nums),但是代码中直接返回i值就行了

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

思路 2 - 时间复杂度: O(lgN) - 空间复杂度: O(1)

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

这题值得一提的随时将上面的移位变成一次移动2位，瞬间beats 100%，可能跟测试用例有关系吧，结果对应索引比较靠前