当前位置: 首页 > news >正文

从零学算法34

34.给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]

  • 非递减数组求区间,很容易想到的是两次二分查找找到左右边界。由于左右边界的找法几乎相同,所以把题目转换一下,只要找到 target 的右边界,我们就知道了结束位置为右边界 - 1;而开始位置,我们只要知道 target - 1 的右边界即可,因为是整数数组,所以只要 target 在数组中存在,那么刚刚大于 target - 1(也就是右边界) 的肯定是 target。这样的话我们只需要把二分查找右边界写成方法,最终返回大致为 [solve(target-1),solve(target)-1] 即可。剩下的就是分析区间不存在的情况。首先数组没数肯定就直接返回了,其次如果我能找到区间。那么可以肯定的是,nums[开始位置] 一定是等于 target 的,不是的话肯定也返回了。还有就是如果所有数都比 target 小,那么起始位置会找到数组外面去,所以二分查找返回的数组下标也应当合法。
  •   public int[] searchRange(int[] nums, int target) {if(nums.length == 0){return new int[]{-1,-1};}int first = solve(nums,target-1);// 需要先判断 first 是否合法,否则 nums[first] 可能直接数组越界了if(first >= nums.length || nums[first] != target){return new int[]{-1,-1};}return new int[]{first,solve(nums,target)-1};}public int solve(int[] nums,int target){int left=0,right=nums.length-1;while(left<=right && left >=0 && right <= nums.length-1){int mid = (left+right)/2;// 这里用小于等于,那么左边界就会不断右移,直到找到大于 target 的第一个数// 所以这里的 left 最后就是 target 的右边界,如果用小于就是左边界了if(nums[mid]<=target)left=mid+1;else right=mid-1;}return left;}
    

相关文章:

从零学算法34

34.给你一个按照非递减顺序排列的整数数组 nums&#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target&#xff0c;返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1&#xff1…...

qiankun-微前端--vue2

项目结构 主应用技术&#xff1a; vue2 子应用技术&#xff1a;vue2 项目目录 这里是特意将主子项目分开来的&#xff0c;方便管理 主应用 安装 qiankun npm install qiankun重新定义一个启动端口&#xff0c;防止和其它子应用共用同一个端口&#xff08;vue.config.js&…...

Win7累积补丁更新包_UpdatePack7R2-23.8.10

UpdatePack7是最新的Win7补丁累积更新包&#xff0c;Windows 7更新补丁安装包&#xff0c;Win7累积更新离线安装包包括所有关键更新和安全更新及Internet Explorer所有版本的更新&#xff0c;此外还集成了NVMe驱动和USB3.0驱动&#xff0c;使用它还可以将累积更新封装到系统内&…...

【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历

理论基础、前中后序遍历的递归法和迭代法、层序遍历 1&#xff0c;二叉树的种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 2&#xff0c;存储方式链式存储线式存储 3&#xff0c;二叉树的遍历深度优先搜索前序遍历&#xff08;递归法、迭代法&#xff09;中序遍历&#xff0…...

Mybatis-plus动态条件查询QueryWrapper的使用

Mybatis-plus动态条件查询QueryWrapper的使用 一&#xff1a;queryWrapper介绍 queryWrapper是mybatis plus中实现查询的对象封装操作类&#xff0c;可以封装sql对象&#xff0c;包括where条件&#xff0c;order by排序&#xff0c;select哪些字段等等&#xff0c;他的层级关…...

Redis安装配置远程连接

1. yum 安装 redis&#xff1a; 直接使用命令&#xff0c;将 redis 安装到 linux 服务器中&#xff1a; yum -y install redis 2. 启动 redis&#xff1a; 在 xshell 里&#xff0c;可以使用下面命令&#xff0c;以后台方式启动 redis&#xff1a; [rootVM-8-17-centos /]…...

pycharm中配置conda

安装好pycharm和conda后&#xff0c;打开pycharm&#xff1a;...

matlab解常微分方程常用数值解法1:前向欧拉法和改进的欧拉法

总结和记录一下matlab求解常微分方程常用的数值解法&#xff0c;本文先从欧拉法和改进的欧拉法讲起。 d x d t f ( x , t ) , x ( t 0 ) x 0 \frac{d x}{d t}f(x, t), \quad x\left(t_{0}\right)x_{0} dtdx​f(x,t),x(t0​)x0​ 1. 前向欧拉法 前向欧拉法使用了泰勒展开的第…...

SQL | 计算字段

7-创建计算字段 7.1-计算字段 存储在数据库中的数据一般不是我们所需要的字段格式&#xff0c; 需要公司名称&#xff0c;同时也需要公司地址&#xff0c;但是这两个数据存储在不同的列中。 省&#xff0c;市&#xff0c;县和邮政编码存储在不同的列中&#xff0c;但是当我们…...

leetcode做题笔记67

给你两个二进制字符串 a 和 b &#xff0c;以二进制字符串的形式返回它们的和。 思路一&#xff1a;模拟题意 void reserve(char* s) {int len strlen(s);for (int i 0; i < len / 2; i) {char t s[i];s[i] s[len - i - 1], s[len - i - 1] t;} }char* addBinary(cha…...

fastadmin 自定义搜索分类和时间范围

1.分类搜索&#xff0c;分类信息获取----php 2.对应html页面&#xff0c;页面底部加搜索提交代码&#xff08;这里需要注意&#xff1a;红框内容&#xff09; 图上代码----方便直接复制使用 <script id"countrySearch" type"text/html"><!--form…...

Oracle Data Redaction与Data Pump

如果表定义了Redaction Policy&#xff0c;导出时数据会脱敏吗&#xff1f;本文解答这个问题。 按照Oracle文档Advanced Security Guide第13章&#xff0c;13.6.5的Tutorial&#xff0c;假设表HR.jobs定义了Redaction Policy。 假设HR用户被授予了访问目录对象的权限&#xf…...

设计模式(6)原型模式

一、介绍 Java中自带的原型模式是clone()方法。该方法是Object的方法&#xff0c;native类型。他的作用就是将对象的在内存的那一块内存数据一字不差地再复制一个。我们写简单类的时候只需要实现Cloneable接口&#xff0c;然后调用Object::clone方法就可实现克隆功能。这样实现…...

pywinauto结合selenium实现文件上传

简介 PC端-Windows上的元素识别可用viewWizard工具 PC端-Windows上的元素操作可用pywinauto库 浏览器上网页的元素识别可用selenium 安装 pip installer pywinauto 使用须知 pywinauto官方文档 确定app的可访问技术 1、win32 API(backend=“win32”) 一般是MFC、VB6、VC…...

【Java多线程学习7】Java线程池技术

线程池技术 一、什么是线程池 线程池顾名思义是管理一组线程的池子。当有任务要处理时&#xff0c;直接从线程池中获取线程来处理&#xff0c;处理完之后线程不会立即销毁&#xff0c;而是等待下一个任务。 二、为什么要使用线程池? 线程池的作用&#xff1f; 1、降低资源…...

VMware虚拟机NAT模式Ubuntu无法上网解决方案

发现只要NAT模式&#xff0c;ping地址时就报网络不可达&#xff0c;且右上方网络图标消失&#xff0c;但是外部USB网络设备又只能在NAT模式下使用。。。 博主的解决方案如下&#xff1a; 按WinR键入services.msc&#xff0c; 找到VMware DHCP Service、VMware NAT Service和V…...

Linux中无法忘记mysql密码处理办法

找到/etc/my.cnf或者/etc/mysql/my.cnf文件 添加下面两行代码&#xff0c;取消密码验证 [mysqld] skip-grant-table使用命令登录&#xff1a;mysql -u root -p&#xff0c;回车&#xff0c;回车使用sql语句来修改密码 mysql>use mysql; mysql>update user set password…...

vue 使用 el-upload 上传文件(自动上传/手动上传)

vue 使用 el-upload 上传文件(自动上传/手动上传) 文章目录 1. 自动上传(选择完文件后,调用axios上传)2.手动上传 1. 自动上传(选择完文件后,调用axios上传) <el-uploadref"upload1"action:multiple"false"accept".xlsx,.csv,.xls":auto-upl…...

服务器遭受攻击之后的常见思路

哈喽大家好&#xff0c;我是咸鱼 不知道大家有没有看过这么一部电影&#xff1a; 这部电影讲述了男主是一个电脑极客&#xff0c;在计算机方面有着不可思议的天赋&#xff0c;男主所在的黑客组织凭借着超高的黑客技术去入侵各种国家机构的系统&#xff0c;并引起了德国秘密警察…...

C语言学习笔记 使用vscode外部console出现闪退-12

前言 在使用vscode的外部console时&#xff0c;会出现闪退现象&#xff0c;这是因为程序运行结束后&#xff0c;系统自动退出了终端&#xff08;终端机制决定的&#xff09;。我们可以在C程序结束后&#xff0c;使用system函数来暂停DOS终端系统&#xff0c;这样就可以完整地看…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...