LeetCode | 搜索插入位置

分类：二分查找 / 数组

题目#

给定一个升序数组 nums 和一个目标值 target。

如果 target 在数组中，返回它的下标；如果不在数组中，返回它应该插入的位置。

示例：

1
输入：nums = [1,3,5,6], target = 5
2
输出：2

1
输入：nums = [1,3,5,6], target = 2
2
输出：1

讲解#

二分法，直接看代码。非常之清晰。二分法的范围通过双指针实现。

复杂度#

暴力做法：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
二分查找：
- 时间复杂度：O(log(n))
- 空间复杂度：O(1)

代码#

源码#

1
from typing import List
2

3

4
class Solution:
5
    def searchInsert(self, nums: List[int], target: int) -> int:
6
        left = 0
7
        right = len(nums)
8

9
        while left < right:
10
            mid = (left + right) // 2
11
            if nums[mid] < target:
12
                left = mid + 1
13
            else:
14
                right = mid
15

16
        return left

测试#

1
from src.python._035_Search_Insert_Position import Solution
2

3

4
sol = Solution()
5

6
assert sol.searchInsert([1, 3, 5, 6], 5) == 2
7
assert sol.searchInsert([1, 3, 5, 6], 2) == 1
8
assert sol.searchInsert([1, 3, 5, 6], 7) == 4
9
assert sol.searchInsert([1, 3, 5, 6], 0) == 0
10

11
print("PASS")

音乐

音乐

题目#

讲解#

复杂度#

代码#

源码#

测试#

参考资料#

文章分享

评论区

音乐

文章目录