Leetcode-35.Search Insert Position

Posted on | | 阅读数
Words count in article: 153 | Reading time ≈ 1

Question

Solution 1

首先，list是排序好的。考虑创建两个前后的指针进行比较。同时需要考虑特殊情况，即target小于第一个元素或者大于最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target <= nums[0]:
            return 0

        for i in range(len(nums)-1):
            idx_bef = nums[i]
            idx_aft = nums[i+1]
            if idx_bef == target:
                return i
            elif idx_aft >= target:
                return i + 1
        return len(nums)

Solution 2

考虑用二分法查找。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (right + left)//2
            if nums[mid] >= target:
                right = mid - 1
            else:
                left = mid + 1
        return left