[ 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将博客内容html导出为Markdown格式

《Python将博客内容html导出为Markdown格式》Python将博客内容html导出为Markdown格式,通过博客url地址抓取文章,分析并提取出文章标题和内容,将内容构建成html,再转... 目录一、为什么要搞?二、准备如何搞?三、说搞咱就搞!抓取文章提取内容构建html转存markdown

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢?我尝试一种更为智能的方法:P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验,

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Python Websockets库的使用指南

《PythonWebsockets库的使用指南》pythonwebsockets库是一个用于创建WebSocket服务器和客户端的Python库,它提供了一种简单的方式来实现实时通信,支持异步和同步... 目录一、WebSocket 简介二、python 的 websockets 库安装三、完整代码示例1.

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专