[LeetCode35]Search Insert Position

2023-11-01 15:32

本文主要是介绍[LeetCode35]Search Insert Position,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Analysis:

could use binary search, there has a additional condition if(mid>left && A[mid]>target && A[mid-1]<target)

Java

public int searchInsert(int[] A, int target) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.int low = 0;int high = A.length-1;if(target < A[0])return 0;if(target > A[A.length-1])return A.length;while(low <= high){int mid = (low+high)/2;if(A[mid]==target)return mid;if(mid>1 && A[mid]>target && A[mid-1]<target) return mid;if(A[mid]>target)high = mid-1;elselow = mid+1;}return 1;}


update

public int searchInsert(int[] nums, int target) {int len = nums.length;if(len<=0) return 0;if(target<=nums[0]) return 0;if(target>nums[len-1]) return len;int left = 0;int right = len-1;while(left<=right) {int mid = left + (right-left)/2;if(nums[mid] == target) return mid;if(nums[mid] > target) {if(target>nums[mid-1]) return mid;else right = mid-1;}else {if(target<nums[mid+1]) return mid+1;else left = mid+1;}}return left;}


c++

int searchInsert(int A[], int n, int target) {if(A == NULL|| target<A[0]) return 0;if(target>A[n-1]) return n;int l = 0;int r = n-1;while(l<=r){int m = (l+r)/2;if(A[m]==target) return m;if(m>l&& A[m]>target && A[m-1]<target) return m;if(A[m]>target)r = m-1;elsel = m+1;}return l; }



这篇关于[LeetCode35]Search Insert Position的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

JavaScript正则表达式六大利器:`test`、`exec`、`match`、`matchAll`、`search`与`replace`详解及对比

在JavaScript中,正则表达式(Regular Expression)是一种用于文本搜索、替换、匹配和验证的强大工具。本文将深入解析与正则表达式相关的几个主要执行方法:test、exec、match、matchAll、search和replace,并对它们进行对比,帮助开发者更好地理解这些方法的使用场景和差异。 正则表达式基础 在深入解析方法之前,先简要回顾一下正则表达式的基础知识。正则

插件maven-search:Maven导入依赖时,使用插件maven-search拷贝需要的依赖的GAV

然后粘贴: <dependency>    <groupId>mysql</groupId>    <artifactId>mysql-connector-java</artifactId>    <version>8.0.26</version> </dependency>

Hibernate插入数据时,报错:org.springframework.dao.DataIntegrityViolationException: could not insert: [cn.itc

在用junit测试:插入数据时,报一下错误: 错误原因: package junit;import org.junit.Test;import cn.itcast.crm.container.ServiceProvinder;import cn.itcast.crm.dao.ISysUserDao;import cn.itcast.crm.domain.SysRole;

css-transform对position:fixed影响

在betterScroll尝试使用position:fixed固定首列,然而并不能实现固定。因为 bscroll / iscroll 是基于 transform 属性实现滚动的, 所以 iscroll 会通过实时修改元素的 transform 属性以达到滚动的效果。父元素如果存在 transform 属性,子元素的 position: fixed 属性无效。betterScroll有个 useTr

广度优先搜索Breadth-First-Search

目录  1.问题 2.算法 3.代码 4.参考文献  1.问题         广度优先搜索,稍微学过算法的人都知道,网上也一大堆资料,这里就不做过多介绍了。直接看问题,还是从下图招到一条从城市Arad到Bucharest的路径。  该图是连通图,所以必然存在一条路径,只是如何找到最短路径。 2.算法 还是贴一个算法的伪代码吧: 1 procedu

【python 编码问题】UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-4: ordinal not

插入oracle 数据发生 错误:UnicodeEncodeError: 'ascii' codec can't encode characters in position 131-136: ordinal not in range(128) 先说解决办法: python2.7版本,在开头加入下面语句 import sysreload(sys)sys.setdefaultencoding

【0323】Postgres内核之 hash table sequentially search(seq_scan_tables、num_seq_scans)

0. seq scan tracking 我们在这里跟踪活跃的 hash_seq_search() 扫描。 需要这种机制是因为如果扫描正在进行时发生桶分裂(bucket split),它可能会访问两次相同的条目,甚至完全错过某些条目(如果它正在访问同一个分裂的桶中的条目)。因此,如果正在向表中插入数据,我们希望抑制桶分裂。 在当前的使用中,这种情况非常罕见,因此只需将分裂推迟到下一次插入即可。

Android Settings搜索Search方案分析

Android开发会遇到一些自写界面需要允许被搜索,或者三方应用挂靠在Settings,用户也希望能被搜索。 在知道怎么添加之前,得先了解下整个框架,才能更好地加入我们自己的代码。   这里稍微整理了下整个search database数据如何索引加载流程。 Settings搜索界面是由SearchFragment展现,当用户在Settings主页中点击搜索图标,会启动到SearchAc

Unexpected token d in JSON at position 5, check bodyParser config错误解决

错误原因:json格式不对 { desc="设备1", iotProjectId=11 } 解决:通过json在线校验格式校验json格式,找出错误原因,修改 在线JSON校验格式化工具(Be JSON) 修改: {"desc": "设备","iotProjectId": 11}