Java每日刷题之二分算法

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

 转化 

 通过题目时间复杂度为O(logN),我们就可以联想到二分算法,但是我们前面学到的算法,是查找出,有序数组里的值,并不是求其中的范围,于是我们可以将找到这个值出现的范围转化为 

通过二分法找到最左边下标以及最右边下标

思路:

1.找到最左边下标

第一步:根据mid的与target的大小进行left和right的移动,如图,当t<=mid,说明最小下标点一定在左边,所以移动right ,  将right赋值给mid,重新进入循环,这样即可得到最左边的下标

2.细节处理

1.当right == left的同时,左端点就是这个点,所以循环条件为left < right

2.在mid范围内mid最大值比最小下标小1,所以left = mid+1;

3.当left和right中间无元素时,取中点方式的不同可能会造成死循环,分析图如下

4.得到值最左边下标

具体思路图如下

2.找到最右边下标

 实现思路

细节处理

由于right 在 t < mid内,所以在t < mid内,想要left 与right 相交,就得right = mid -1; 

取中间点的方法和上面找到最左边下标思路相同

注意 

考虑没有target值和数组为空的情况

代码实现

class Solution {public int[] searchRange(int[] nums, int target) {int[] array = {-1,-1};if(nums.length == 0) return array;//找到左边界点int left = 0,right = nums.length-1;while(left<right){int mid = left +(right-left)/2;if(nums[mid] < target){left = mid+1;}else{right = mid;}}if(nums[left] != target) return array;else{array[0] = left;}//找到右边界点 left = 0;right = nums.length-1;while(left<right){int mid = left +(right-left+1)/2;if(nums[mid] > target){right = mid-1;}else{left = mid;}}if(nums[left] != target) return array;else{array[1] = right;} return array;}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/384.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

qt QBrush详解

1、概述 QBrush是Qt框架中的一个基本图形对象类&#xff0c;它主要用于定义图形的填充模式。QBrush可以用于填充如矩形、椭圆形、多边形等形状&#xff0c;也可以用于绘制背景等。通过QBrush&#xff0c;可以设置填充的颜色、样式&#xff08;如实心、渐变、纹理等&#xff09…

postman如何安装旧版本不升级(以9.31和11.10版本为例)

postman版本超过10.x&#xff08;包含10.x)&#xff0c;有个大的麻烦&#xff0c;就是需要登录账号&#xff0c;如果网络不佳&#xff08;其实是外网受限&#xff09;,那就很难受了 功能页面都进不去了&#xff01;而8.x /9.x等以下版本就不需要登录了。 比如9.31.30这个版本就…

线程函数和线程启动的几种不同形式

线程函数和线程启动的几种不同形式 在C中&#xff0c;线程函数和线程启动可以通过多种形式实现。以下是几种常见的形式&#xff0c;并附有相应的示例代码。 1. 使用函数指针启动线程 最基本的方式是使用函数指针来启动线程。 示例代码&#xff1a; #include <iostream&g…

Arm和高通闹翻在即,或影响骁龙 8 Elite

原文转载修改自&#xff08;更多互联网新闻/搞机小知识&#xff09;&#xff1a; Arm向高通下达最后通牒&#xff0c;骁龙 8 Elite或受影响 其实对于小江这个不咋关注安卓圈的用户来说&#xff0c;高通和Arm大概就是秤不离砣&#xff0c;砣不离秤的关系。不过在看了今天的最新…

【学术精选】SCI期刊《Electronics》特刊“New Challenges in Remote Sensing Image Processing“

英文名称&#xff1a;New Challenges in Remote Sensing Image Processing 中文名称&#xff1a;"遥感图像处理的新挑战"特刊 期刊介绍 “New Challenges in Remote Sensing Image Processing”特刊隶属于《Electronics》期刊&#xff0c;聚焦遥感图像处理领域快速…

人机环境系统智能是东方天地人思想与西方科技思维的融合

西方科技思维常常受到还原主义的影响&#xff0c;这种思维方式通常强调将复杂系统拆解为更简单的部分进行分析&#xff08;比如物理的分子、原子、电子、夸克……&#xff0c;数理中的分解因式&#xff09;。以下是还原主义的一些特点&#xff1a; 分析方法&#xff1a;强调通过…

深度学习:梯度下降算法简介

梯度下降算法简介 梯度下降算法 我们思考这样一个问题&#xff0c;现在需要用一条直线来回归拟合这三个点&#xff0c;直线的方程是 y w ^ x b y \hat{w}x b yw^xb&#xff0c;我们假设斜率 w ^ \hat{w} w^是已知的&#xff0c;现在想要找到一个最好的截距 b b b。 一条…

瑞芯微RK3566/RK3568 Android11下该如何默认屏蔽导航栏/状态栏?看这篇文章就懂了

本文介绍瑞芯微RK3566/RK3568在Android11系统下&#xff0c;默认屏蔽导航栏/状态栏方法&#xff0c;使用触觉智能Purple Pi OH鸿蒙开发板演示&#xff0c;搭载了瑞芯微RK3566芯片&#xff0c;类树莓派设计&#xff0c;Laval官方社区主荐&#xff0c;已适配全新OpenHarmony5.0 R…

Python | Leetcode Python题解之第519题随机翻转矩阵

题目&#xff1a; 题解&#xff1a; class Solution:def __init__(self, m: int, n: int):self.m mself.n nself.total m * nself.map {}def flip(self) -> List[int]:x random.randint(0, self.total - 1)self.total - 1# 查找位置 x 对应的映射idx self.map.get(x,…

从0学习React(6)

这两天在写IT资产管理的时候&#xff0c;对于前端&#xff0c;我一直没有任何头绪&#xff0c;不知道怎么写。因为我之前并没有学习过前端方面的知识&#xff0c;我学的都是后端。我在写后端接口的时候&#xff0c;我是自己有一些基础的&#xff0c;然后我又参照着模仿着一些很…

单个相机矫正畸变

1、通过标定助手获取到内参外参&#xff0c;外参在此无效&#xff0c;只用到了内参 2、然后通过halcon算子进行矫正 参考&#xff1a;超人视觉

乘云而上,OceanBase再越山峰

一座山峰都是一个挑战&#xff0c;每一次攀登都是一次超越。 商业数据库时代&#xff0c;面对国外数据库巨头这座大山&#xff0c;实现市场突破一直都是中国数据库产业多年夙愿&#xff0c;而OceanBase在金融核心系统等领域的攻坚克难&#xff0c;为产业突破交出一副令人信服的…

laravel: Breeze 和 Blade, 登录 注册等

composer require laravel/breeze --dev php artisan breeze:install php artisan migrate npm install npm run build php artisan route:clear http://laravel-dev.cn/ http://laravel-dev.cn/register http://laravel-dev.cn/login

VS+Qt解决提升控件后,包含头文件格式不对问题处理

一、前言 VSQt 提升控件后&#xff0c;在uic目录下会生成ui相关的初始化文件&#xff0c;对于提升的控件头文件包含的格式为#include<> 而非 #include “ ” 导致无法找到头文件。如果手动修改为 #include “ ”相当麻烦&#xff0c;甚至每次编译都要修改一遍&#xff0c…

一些硬件知识【2024/11/3】

MLCC电容的ESR比较小&#xff0c;但是他的缺点是容量通常比较低&#xff1b;电解电容的容量比较大&#xff0c;但是他的ESR比较大&#xff1b;而钽电容介于两者之间&#xff0c;是MLCC找不到合适的容值比较大的时候&#xff0c;找钽电容&#xff1a; LC谐振电路&#xff1a; 五…

简单的ELK部署学习

简单的ELK部署学习 1. 需求 我们公司现在使用的是ELK日志跟踪&#xff0c;在出现问题的时候&#xff0c;我们可以快速定为到问题&#xff0c;并且可以对日志进行分类检索&#xff0c;比如对服务名称&#xff0c;ip , 级别等信息进行分类检索。此文章为本人学习了解我们公司的…

SpringBoot篇(自动装配原理)

目录 一、自动装配机制 1. 简介 2. 自动装配主要依靠三个核心的关键技术 3. run()方法加载启动类 4. 注解SpringBootApplication包含了多个注解 4.1 SpringBootConfiguration 4.2 ComponentScan 4.3 EnableAutoConfiguration 5. SpringBootApplication一共做了三件事 …

科学减肥:基础代谢减肥法

基础代谢减肥法是什么&#xff1f; 相信有很多人在减肥的路上都有做过努力&#xff0c;但是效果往往和努力不匹配。那是因为很多时候在细节上面没有做对&#xff0c;大家都是根据自己的理解去努力&#xff0c;而没有深度去了解过身体营养成分构成与吸收。 没科学了解过减肥的原…

华为云安装docker

docker_docker-compose_install: 代替官网的一键安装脚本&#xff0c;使用docker包进行离线安装 bash <(curl -sL https://raw.githubusercontent.com/1scripts/docker_docker-compose_install/main/quick_install.sh) 华为镜像&#xff1a; https://console.huaweicloud.…

中欧科学家论坛暨第六届人工智能与先进制造国际会议(AIAM 2024)在德国法兰克福成功举办,两百余名中外科学家共襄盛举

2024年10月20至21日&#xff0c;首届中欧科学家论坛在德国法兰克福的SAALBAU Titus Forum国际会议中心成功举行。中国驻法兰克福总领事馆伍鹏飞副总领事、德国兰斯巴赫-鲍姆巴赫市市长Michael Merz亲自出席并致辞。2004年诺贝尔化学奖得主Aaron Ciechanover教授和法国国家科学院…