自定义网站建设,手机版自媒体135免费下载,搭建平台有哪些平台说法,wordpress 显示浏览量题目难度: 简单 原题链接 今天继续更新 Leetcode 的剑指 Offer#xff08;专项突击版#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
给定一个排序的整数数组 nums 和一个整数目标值 target #xf… 题目难度: 简单 原题链接 今天继续更新 Leetcode 的剑指 Offer专项突击版系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
给定一个排序的整数数组 nums 和一个整数目标值 target 请在数组中找到 target 并返回其下标。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5输出: 2
示例 2:
输入: nums [1,3,5,6], target 2输出: 1
示例 3:
输入: nums [1,3,5,6], target 7输出: 4
示例 4:
输入: nums [1,3,5,6], target 0输出: 0
示例 5:
输入: nums [1], target 0输出: 0
提示:
1 nums.length 10^4-10^4 nums[i] 10^4nums 为无重复元素的升序排列数组-10^4 target 10^4
题目思考
如何利用数组的有序性?
解决方案
思路
分析题目, 一个最直接的思路就是遍历数组, 返回第一个大于等于 target 的下标, 没有的话则返回数组长度作为插入位置不过这样做的时间复杂度达到了 O(N), 不满足题目要求, 如何优化呢?由于数组有序, 所以我们可以利用经典的二分查找来找 target如果 target 存在于数组中, 则二分查找到对应下标后直接返回如果 target 不存在于数组中, 则其插入位置是第一个值大于 target 的下标, 或者数组长度 (当所有值都小于 target 时)具体做法如下: 初始化插入位置 res 为数组长度 (最大的插入位置)初始化左右边界 s 和 e 分别为 0 和最后一个下标, 代表查找整个数组使用 while 循环保证当前查找范围有效, 即满足 se计算当前两者中点 m, 并比较对应的值和 target 的关系如果中点值等于 target, 则说明找到了 target, 直接返回其下标 m如果中点值小于 target, 则 m 不可能是插入位置, 直接将 s 设置为 m1, 继续查找右半部分如果中点值大于 target, 则 m 可能是插入位置, 更新 res 为 res 和 m 的较小值, 然后将 e 设置为 m-1, 继续查找左半部分最后, 遍历完所有前缀长度后的 res 即为所求 下面代码中有详细的注释, 方便大家理解
复杂度
时间复杂度 O(logN): 二分查找每次都会将问题规模减半, 所以是 O(logN)空间复杂度 O(1): 只使用了几个常数空间的变量
代码
class Solution:def searchInsert(self, nums: List[int], target: int) - int:# 因为插入位置可能是数组末尾, 所以res要初始化为数组长度res len(nums)s, e 0, len(nums) - 1while s e:m (s e) 1if nums[m] target:# 找到target了, 返回下标return melif nums[m] target:# 当前数字小于target, 一定不可能是插入位置s m 1else:# 当前数字大于target, 可能是插入位置, res更新为两者较小值res min(res, m)e m - 1return res大家可以在下面这些地方找到我~ 我的 GitHub 我的 Leetcode 我的 CSDN 我的知乎专栏 我的头条号 我的牛客网博客 我的公众号: 算法精选, 欢迎大家扫码关注~
