Go语言题解LeetCode35搜索插入位置示例详解
作者:刘09k11 发布时间:2023-07-16 17:17:00
标签:Go,LeetCode,搜索,插入位置
题目描述
原题链接 :
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;
}
}
代码
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;
}
}
来源:https://juejin.cn/post/7173274268069953572
0
投稿
猜你喜欢
- 很多时候,我们都需要获取windows消息提示框的文本内容,例如系统异常信息,软件错误提示等。。。但是如何获取提示信息呢?通常我们的印象中,
- 作用域链(Scope Chain)JavaScript中的一种重要机制,JS中所有的标识符(Identifier)都是通过Scope Cha
- ul设置浮动后不能自适应高度,也就是不能撑开父容器,不能自适应内容的高度。解决方法是在ul结束标签前加个清除浮动。 &
- 将表数据生成SQL脚本的存储过程示例:CREATE PROCEDURE dbo.UspOutputData @tablename sysna
- SpringBoot体系内推荐使用Thymeleaf作为前端页面模板。jsp还得自己整合一下。1.项目结构对比以前的项目结构,main目录下
- 实验目的:验证主动释放内存变量是否有价值. 实验原始代码: <script language=vbscript runat=serve
- 优化数据库的注意事项:1、关键字段建立索引。2、使用存储过程,它使SQL变得更加灵活和高效。3、备份数据库和清除垃圾数据。4、SQL语句语法
- 在multiIndex中选定指定索引的行我们在用pandas类似groupby来使用多重index时,有时想要对多个level中的某个ind
- 本文描述通过统计分析出医院信息系统需分区的表,对需分区的表选择分区键,即找出包括在你的分区键中的列(表的属性),对大型数据的管理比较有意义,
- 第一种方法: 分为 大 中 小 控制正文字体大小,一般需要指定 id<!DOCTYPE html PUBLIC "-//W3
- 如何做一个文本书写器?我们有下面的的函数,可做“文本书写器”:<%function WriteToFile(FileName
- 除了IE浏览器,其他所有主流的浏览器均支持原生的 Base64 编码:btoa(text) – base64 encodes text. a
- 废话不多说了,直接给大家贴js代码了,具体代码如下所示:<!DOCTYPE html><html><head&
- 英文原文:http://www.456bereastreet.com/archive/200601/css_3_selectors_expl
- 本文实例为大家分享了js浏览器倒计时跳转页面效果,供大家参考,具体内容如下效果图:<!DOCTYPE html><html
- Demo里的三种方法:方法1是两层div,兼容FF3.1a+, Safari 3+, Chrome, IE6/7方法2是两层div,除了IE
- IE的有条件注释是一种专有的(因此是非标准的)、对常规(X)HTML注释的Miscrosoft扩展。顾名思义,有条件注释使你能够根据条件(比
- EXEC SQL WHENEVER SQLERROR CONTINUE; sqlglm(msg_buffer, &buf
- 参数Parameters解析响应时间resolveTimeout 数据类型:长整型。简单地说就是程序对目标主机的名字解析解析的一个过程时间。
- 如果独自放着jQuery做事,它绝对做得很好,但jQuery充许与其他库共存在,有些事就防不胜防了。看下面代码data :func