[ LeetCode ] 题刷刷(Python)-第35题:搜索插入位置

2024-04-22 08:44

本文主要是介绍[ LeetCode ] 题刷刷(Python)-第35题:搜索插入位置,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

nums 为 无重复元素升序 排列数组

请必须使用时间复杂度为 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

解题

解法一: 二分查找

思路

二分查找(Binary Search)是一种基于比较的搜索算法,适用于已排序(升序或降序)的有序序列(如数组)。其基本思想如下:

1、初始化:确定搜索范围,通常是整个有序数组。设数组的左边界为 left,右边界为 right。

2、迭代:在每一步迭代中,计算中间索引 mid,通常是取 left 和 right 的平均值(向下取整)

(1)直接取平均值:mid = (left + right) // 2
(2)避免整数溢出:mid = left + (right - left) // 2

3、比较:将中间元素 nums[mid] 与目标值 target 进行比较:

(1)相等:如果 nums[mid] 等于 target,则找到目标值,返回 mid 作为其索引。
(2)小于:如果 nums[mid] 小于 target,说明目标值可能位于 mid 右侧的子数组中,因此缩小搜索范围至右半部分,即更新 left = mid + 1。
(3)大于:如果 nums[mid] 大于 target,说明目标值可能位于 mid 左侧的子数组中,因此缩小搜索范围至左半部分,即更新 right = mid - 1。
4、终止条件:重复步骤2和步骤3,直到找到目标值或者左右边界相遇(left > right),此时表明目标值不在数组中。

算法复杂度

时间复杂度:O(log⁡n),其中 n为数组的长度。


空间复杂度:O(1)。

代码

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:# 定义左右指针left, right = 0, len(nums) - 1# 如果左指针不大于右指针while left <= right:# 计算中间索引mid(防止整数溢出)mid = left + (right - left) // 2# 如果 nums[mid] 等于 target,则找到目标值,返回 mid 作为其索引。if nums[mid] == target:return mid# 如果 nums[mid] 小于 target,说明目标值可能位于 mid 右侧的子数组中# 因此缩小搜索范围至右半部分,即更新 left = mid + 1。elif nums[mid] < target:left = mid + 1# 如果 nums[mid] 大于 target,说明目标值可能位于 mid 左侧的子数组中# 因此缩小搜索范围至左半部分,即更新 right = mid - 1。else:right = mid - 1# 当 left > right 时,退出循环。# 此时 left 指向的目标位置即为目标值应插入的位置return left

解法二: 使用内置函数 bisect_left

思路

一行代码,不讲武德。

bisect_left 是 Python 标准库 bisect 模块提供的一个函数,专门用于已排序序列(如列表)的二分查找。这个函数的主要作用是返回目标值应该插入的索引,使得插入后列表依然保持有序。

算法复杂度

时间复杂度:O(log⁡n),其中 n为数组的长度。


空间复杂度:O(1)。

代码

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:return bisect_left(nums, target)

解法三: 线性查找(时间复杂度不满足)

思路

从数组的第一个元素开始,逐个比较每个元素与目标值,直到找到目标值或遍历完整个数组。找到目标值时返回其索引,未找到时返回应插入的位置。

算法复杂度

时间复杂度:O(⁡n),其中 n为数组的长度。


空间复杂度:O(1)。

代码

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:for i, num in enumerate(nums):# 如果当前num等于目标值target,返回其下标if num == target:return i# 如果当前num大于目标值target,返回其下标# 因为是升序无重复元素数,你比我大,我该排你这里# [1,2,4,5],target=3;4>3-->[1,2,3,4,5]elif num > target:return i# 都不满足,说明应插入最后的位置return len(nums)

这篇关于[ LeetCode ] 题刷刷(Python)-第35题:搜索插入位置的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

利用python实现对excel文件进行加密

《利用python实现对excel文件进行加密》由于文件内容的私密性,需要对Excel文件进行加密,保护文件以免给第三方看到,本文将以Python语言为例,和大家讲讲如何对Excel文件进行加密,感兴... 目录前言方法一:使用pywin32库(仅限Windows)方法二:使用msoffcrypto-too

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

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

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

python获取网页表格的多种方法汇总

《python获取网页表格的多种方法汇总》我们在网页上看到很多的表格,如果要获取里面的数据或者转化成其他格式,就需要将表格获取下来并进行整理,在Python中,获取网页表格的方法有多种,下面就跟随小编... 目录1. 使用Pandas的read_html2. 使用BeautifulSoup和pandas3.

Python装饰器之类装饰器详解

《Python装饰器之类装饰器详解》本文将详细介绍Python中类装饰器的概念、使用方法以及应用场景,并通过一个综合详细的例子展示如何使用类装饰器,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录1. 引言2. 装饰器的基本概念2.1. 函数装饰器复习2.2 类装饰器的定义和使用3. 类装饰

Python 交互式可视化的利器Bokeh的使用

《Python交互式可视化的利器Bokeh的使用》Bokeh是一个专注于Web端交互式数据可视化的Python库,本文主要介绍了Python交互式可视化的利器Bokeh的使用,具有一定的参考价值,感... 目录1. Bokeh 简介1.1 为什么选择 Bokeh1.2 安装与环境配置2. Bokeh 基础2

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技