Leetcode 剑指 Offer II 068.搜索插入位置

2024-03-10 05:20

本文主要是介绍Leetcode 剑指 Offer II 068.搜索插入位置,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目难度: 简单

原题链接

今天继续更新 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^4
  • nums 为无重复元素的升序排列数组
  • -10^4 <= target <= 10^4

题目思考

  1. 如何利用数组的有序性?

解决方案

思路
  • 分析题目, 一个最直接的思路就是遍历数组, 返回第一个大于等于 target 的下标, 没有的话则返回数组长度作为插入位置
  • 不过这样做的时间复杂度达到了 O(N), 不满足题目要求, 如何优化呢?
  • 由于数组有序, 所以我们可以利用经典的二分查找来找 target
  • 如果 target 存在于数组中, 则二分查找到对应下标后直接返回
  • 如果 target 不存在于数组中, 则其插入位置是第一个值大于 target 的下标, 或者数组长度 (当所有值都小于 target 时)
  • 具体做法如下:
    1. 初始化插入位置 res 为数组长度 (最大的插入位置)
    2. 初始化左右边界 s 和 e 分别为 0 和最后一个下标, 代表查找整个数组
    3. 使用 while 循环保证当前查找范围有效, 即满足 s<=e
    4. 计算当前两者中点 m, 并比较对应的值和 target 的关系
    5. 如果中点值等于 target, 则说明找到了 target, 直接返回其下标 m
    6. 如果中点值小于 target, 则 m 不可能是插入位置, 直接将 s 设置为 m+1, 继续查找右半部分
    7. 如果中点值大于 target, 则 m 可能是插入位置, 更新 res 为 res 和 m 的较小值, 然后将 e 设置为 m-1, 继续查找左半部分
    8. 最后, 遍历完所有前缀长度后的 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

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我

这篇关于Leetcode 剑指 Offer II 068.搜索插入位置的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/793184

相关文章

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

Python中bisect_left 函数实现高效插入与有序列表管理

《Python中bisect_left函数实现高效插入与有序列表管理》Python的bisect_left函数通过二分查找高效定位有序列表插入位置,与bisect_right的区别在于处理重复元素时... 目录一、bisect_left 基本介绍1.1 函数定义1.2 核心功能二、bisect_left 与

解决mysql插入数据锁等待超时报错:Lock wait timeout exceeded;try restarting transaction

《解决mysql插入数据锁等待超时报错:Lockwaittimeoutexceeded;tryrestartingtransaction》:本文主要介绍解决mysql插入数据锁等待超时报... 目录报错信息解决办法1、数据库中执行如下sql2、再到 INNODB_TRX 事务表中查看总结报错信息Lock

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

PyCharm如何更改缓存位置

《PyCharm如何更改缓存位置》:本文主要介绍PyCharm如何更改缓存位置的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录PyCharm更改缓存位置1.打开PyCharm的安装编程目录2.将config、sjsystem、plugins和log的路径

SpringBoot整合mybatisPlus实现批量插入并获取ID详解

《SpringBoot整合mybatisPlus实现批量插入并获取ID详解》这篇文章主要为大家详细介绍了SpringBoot如何整合mybatisPlus实现批量插入并获取ID,文中的示例代码讲解详细... 目录【1】saveBATch(一万条数据总耗时:2478ms)【2】集合方式foreach(一万条数

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Jmeter如何向数据库批量插入数据

《Jmeter如何向数据库批量插入数据》:本文主要介绍Jmeter如何向数据库批量插入数据方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Jmeter向数据库批量插入数据Jmeter向mysql数据库中插入数据的入门操作接下来做一下各个元件的配置总结Jmete

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

使用Python在Excel中插入、修改、提取和删除超链接

《使用Python在Excel中插入、修改、提取和删除超链接》超链接是Excel中的常用功能,通过点击超链接可以快速跳转到外部网站、本地文件或工作表中的特定单元格,有效提升数据访问的效率和用户体验,这... 目录引言使用工具python在Excel中插入超链接Python修改Excel中的超链接Python