Go语言题解LeetCode35搜索插入位置示例详解

目录
  • 题目描述
    • 思路分析
    • AC 代码
  • 总结
  • 优先考虑边界情况 红蓝标记解法
    • 代码

题目描述

原题链接 :

35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)

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

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

提示:

1 <= nums.length <= 10^4

-10^4 <= nums[i] <= 10^4

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

-10^4 <= target <= 10^4

思路分析

首先明确题目的含义：

（1）数组是有序的；

（2）如果含有与目标值相等，则返回目标值下标，若不同，则按顺序排序获取下标

思路：采用二分搜索法的策略，获取中间数据的大小，缩短数组的大小定位区间，如在数组中间的前一段，数组中间的后一段

获取下标i的值arrs[i]>=target,进行相应的下标返回

AC 代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int index = (nums.length / 2);
        if (nums[index] >= target) {
            return compareByIndex(nums, 0, index+1, target);
        } else
            return compareByIndex(nums, index+1, nums.length, target);
    }
    private int compareByIndex(int[] nums, int start, int end, int target) {
        for (int i = start; i < end; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return end;
    }
}

总结

这种查找位置的，肯定二分法是合适的，即使不能直接套用二分法的公式，也是二分法的思想，变种。

参考

️思维导图整理: 总结了二分查找的通用模板写法, 彻底解决几个易混淆问题️ - 搜索插入位置

优先考虑边界情况 红蓝标记解法

首先考虑target是否>=nums[numsSize-1],大于则返回numsSize，等于则返回numsSize-1;

再检查底线，若小于等于nums[0]则返回nums[0]；

else

定义左边界left=0，右边界right=numsSize-1；

进入循环，缩小边界，直到left+1=right；

若找到则直接返回，循环结束时未找到则返回left+1（在left与right之间）

代码

int searchInsert(int* nums, int numsSize, int target){
    if(nums[0]>=target)
    {
        return 0;
    }
    else if(nums[numsSize-1]<target)
    {
         return numsSize;
    }
    else if(nums[numsSize-1]==target)
    {
        return numsSize-1;
    }
    else{
         int r=numsSize-1;
         int i=0;
    while(i+1!=r)
    {
        int mid=(i+r)/2;
    if(nums[mid]>target )
{
    r=mid;
}
        else if(nums[mid]<target)
                 i=mid;
        else{
                 return mid;
 }
    }
            return i+1;

    }
}

以上就是Go语言题解LeetCode35搜索插入位置示例详解的详细内容，更多关于Go语言搜索插入位置的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 详解Golang中select的使用与源码分析

    目录 背景 select 流程 背景 golang 中主推 channel 通信.单个 channel 的通信可以通过一个goroutine往 channel 发数据,另外一个从channel取数据进行.这是阻塞的,因为要想顺利执行完这个步骤,需要 channel 准备好才行,准备好的条件如下: 1.发送 缓存有空间(如果是有缓存的 channel) 有等待接收的 goroutine 2.接收 缓存有数据(如果是有缓存的 channel) 有等待发送的 goroutine 对channel实际使

  • go slice 扩容实现原理源码解析

    目录 正文 扩容的示例 实际扩容倍数 growslice 实现 growslice 实现步骤 growslice 源码剖析 总结 正文 基于 Go 1.19. go 的切片我们都知道可以自动地进行扩容,具体来说就是在切片的容量容纳不下新的元素的时候, 底层会帮我们为切片的底层数组分配更大的内存空间,然后把旧的切片的底层数组指针指向新的内存中: 目前网上一些关于扩容倍数的文章都是基于相对旧版本的 Go 的,新版本中,现在切片扩容的时候并不是那种准确的小于多少容量的时候就 2 倍扩容, 大于多少容量

  • go sync Waitgroup数据结构实现基本操作详解

    目录 WaitGroup 示例 WaitGroup 基本原理 背景知识 信号量 WaitGroup 中的信号量 WaitGroup 数据结构 noCopy state sema WaitGroup 的三个基本操作 WaitGroup 的实现 Add 的实现 Done 的实现 Wait 的实现 总结 WaitGroup 示例 本文基于 Go 1.19. go 里面的 WaitGroup 是非常常见的一种并发控制方式,它可以让我们的代码等待一组 goroutine 的结束. 比如在主协程中等待几个子

  • go reflect要不要传指针原理详解

    目录 正文 什么时候传递指针? 1. 通过传递指针修改变量的值 传值无法修改变量本身 传指针可以修改变量 2. 通过传递指针修改结构体的字段 3. 结构体:获取指针接收值方法 4. 变量本身包含指向数据的指针 通过值反射对象修改 chan.map 和 slice slice 反射对象扩容的影响 slice 容量够的话是不是就可以正常追加元素了? map 也不能通过值反射对象来修改其元素. chan 没有追加 结构体字段包含指针的情况 5. interface 类型处理 interface 底层类

  • go sync Once实现原理示例解析

    目录 正文 Once 的实现 使用示例 Once 的一些工作机制 Once 详解 hotpath atomic.LoadUint32 atomic.StoreUint32 Mutex 总结 正文 在很多情况下,我们可能需要控制某一段代码只执行一次,比如做某些初始化操作,如初始化数据库连接等. 对于这种场景,go 为我们提供了 sync.Once 对象,它保证了某个动作只被执行一次. 当然我们也是可以自己通过 Mutex 实现 sync.Once 的功能,但是相比来说繁琐了那么一点, 因为我们不仅

  • go语言题解LeetCode66加一示例详解

    目录 题目描述 思路分析 AC 代码 小结 JavaScript 66题 代码 python3 循环判断 分析: JAVA解决进位问题 解题思路 代码 题目描述 原题链接 : 66. 加一 给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一. 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字. 你可以假设除了整数 0 之外,这个整数不会以零开头. 示例 1: 输入:digits = [1,2,3] 输出:[1,2,4] 解释:输入数组表示数字 123. 示例 2:

  • Go语言题解LeetCode455分发饼干示例详解

    目录 题目描述 思路分析 AC 代码 分发饼干 贪心算法 解题思路 代码 题目描述 原题链接 : 455. 分发饼干 - 力扣(LeetCode) (leetcode-cn.com) 假设你是一位很棒的家长,想要给你的孩子们一些小饼干.但是,每个孩子最多只能给一块饼干. 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸:并且每块饼干 j,都有一个尺寸 s[j] .如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足.你的目标

  • go语言题解LeetCode506相对名次示例详解

    目录 一 描述 二 分析 三 答案 一 描述 506. 相对名次 给你一个长度为 n 的整数数组 score ,其中 score[i] 是第 i 位运动员在比赛中的得分.所有得分都 互不相同 . 运动员将根据得分 决定名次 ,其中名次第 1 的运动员得分最高,名次第 2 的运动员得分第 2 高,依此类推.运动员的名次决定了他们的获奖情况: 名次第 1 的运动员获金牌 "Gold Medal" . 名次第 2 的运动员获银牌 "Silver Medal" . 名次第

  • go语言题解LeetCode1160拼写单词示例详解

    目录 题目描述 思路分析 AC 代码 别人用int[26] 解题思路 代码 c++几乎双百的哈希解法 代码 题目描述 1160. 拼写单词 - 力扣(LeetCode) 给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars. 假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词. 注意:每次拼写(指拼写词汇表中的一个单词)时,chars 中的每个字母都只能用一次. 返回词汇表 words 中你

  • C语言中的正则表达式使用示例详解

    正则表达式,又称正规表示法.常规表示法(英语:Regular Expression,在代码中常简写为regex.regexp或RE).正则表达式是使用单个字符串来描述.匹配一系列符合某个句法规则的字符串. 在c语言中,用regcomp.regexec.regfree 和regerror处理正则表达式.处理正则表达式分三步: 编译正则表达式,regcomp: 匹配正则表达式,regexec: 释放正则表达式,regfree. 函数原型 /* 函数说明:Regcomp将正则表达式字符串regex编译

  • VSCode各语言运行环境配置方法示例详解

    系统环境变量的配置 如:将F:\mingw64\bin添加到系统环境变量Path中 VSCode软件语言json配置C语言 创建个.vscode文件夹,文件夹内创建以下两个文件 launch.json 文件配置 { "version": "0.2.0", "configurations": [ { "name": "(gdb) Launch", "type": "cppdbg&

  • c语言左移和右移的示例详解

    逻辑移位,简单理解就是物理上按位进行的左右移动,两头用0进行补充,不关心数值的符号问题. 算术移位,同样也是物理上按位进行的左右移动,两头用0进行补充,但必须确保符号位不改变. 算术移位指令 算术移位指令有:算术左移SAL(ShiftAlgebraic Left)和算术右移SAR(ShiftAlgebraic Right).算术移位指令的功能描述如下: (1)算术左移SAL把目的操作数的低位向高位移,空出的低位补0: (2)算术右移SAR把目的操作数的高位向低位移,空出的高位用最高位(符号位)填

  • R语言时间序列TAR阈值自回归模型示例详解

    R语言时间序列TAR阈值自回归模型示例详解

    为了方便起见,这些模型通常简称为TAR模型.这些模型捕获了线性时间序列模型无法捕获的行为,例如周期,幅度相关的频率和跳跃现象.Tong和Lim(1980)使用阈值模型表明,该模型能够发现黑子数据出现的不对称周期性行为. 一阶TAR模型的示例: σ是噪声标准偏差,Yt-1是阈值变量,r是阈值参数, {et}是具有零均值和单位方差的iid随机变量序列. 每个线性子模型都称为一个机制.上面是两个机制的模型. 考虑以下简单的一阶TAR模型: #低机制参数 i1 = 0.3 p1 = 0.5 s1 = 1

  • C语言实现冒泡排序算法的示例详解

    C语言实现冒泡排序算法的示例详解

    目录 1. 问题描述 2. 问题分析 3. 算法设计 动图演示 4. 程序设计 设计一 设计二 结论 5. 流程框架 6. 代码实现 7. 问题拓展 1. 问题描述 对N个整数(数据由键盘输入)进行升序排列. 2. 问题分析 对于N个数因其类型相同,我们可利用 数组 进行存储. 冒泡排序是在 两个相邻元素之间进行比较交换的过程将一个无序表变成有序表. 冒泡排序的思想:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小. 若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,

  • Go语言使用对称加密的示例详解

    目录 介绍 AES 算法 实践 总结 介绍 在项目开发中,我们经常会遇到需要使用对称密钥加密的场景,比如客户端调用接口时,参数包含手机号.身份证号或银行卡号等. 对称密钥加密是一种加密方式,其中只有一个密钥用于加密和解密数据.通过对称加密进行通信的实体必须共享该密钥,以便可以在解密过程中使用它.这种加密方法与非对称加密不同,非对称加密使用一对密钥(一个公钥和一个私钥)来加密和解密数据. AES 算法 常见的对称密钥加密算法有 AES (Advanced Encryption Standard),

随机推荐