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

相关文章

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

如何用Java结合经纬度位置计算目标点的日出日落时间详解

《如何用Java结合经纬度位置计算目标点的日出日落时间详解》这篇文章主详细讲解了如何基于目标点的经纬度计算日出日落时间,提供了在线API和Java库两种计算方法,并通过实际案例展示了其应用,需要的朋友... 目录前言一、应用示例1、天安门升旗时间2、湖南省日出日落信息二、Java日出日落计算1、在线API2

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大