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

二分查找算法专题(2)

找往期文章包括但不限于本期文章中不懂的知识点:

个人主页:我要学编程(ಥ_ಥ)-CSDN博客

所属专栏: 优选算法专题

对于二分查找算法不是很了解或者只了解一部分的小伙伴一定要去看下面这篇博客:二分查找算法的介绍与另外一种查找方法的推导

目录

852. 山脉数组的峰顶索引

162. 寻找峰值

153. 寻找旋转排序数组中的最小值

LCR. 173.点名


852. 山脉数组的峰顶索引

题目:

给定一个长度为 n 的整数 山脉 数组 arr ,其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1:

输入:arr = [0,1,0]
输出:1

示例 2:

输入:arr = [0,2,1,0]
输出:1

示例 3:

输入:arr = [0,10,5,2]
输出:1

提示:

  • 3 <= arr.length <= 105
  • 0 <= arr[i] <= 106
  • 题目数据 保证 arr 是一个山脉数组

思路:题目就是让我们找出数组中的最大值。暴力枚举应该是非常容易想到的。

代码实现:

暴力枚举:

class Solution {public int peakIndexInMountainArray(int[] arr) {// 遍历数组寻找最大值int max = 0;for (int i = 1; i < arr.length; i++) {if (arr[i] > arr[max]) {max = i;} else { // max此时就是最大值break;}}return max;}
}

我们仔细观察会发现数组有一个特点:先是按照严格的升序排列,再是按照严格的降序排列。这也就是我们所说的二段性,即可以使用二分查找算法来解决问题。

代码实现:

峰值在右边区域:

class Solution {public int peakIndexInMountainArray(int[] arr) {// 二分查找寻找峰值int left = 1;int right = arr.length-2;while (left < right) {int mid = left + (right - left) / 2;// 峰值存在于右边区间,因此只能和右区间进行比较,而不能跑到左边区间去if (arr[mid] < arr[mid+1]) {// 落在左边区域left = mid+1;} else {// 落在右边区域right = mid;}}return left;}
}

峰值在左边区域:

class Solution {public int peakIndexInMountainArray(int[] arr) {// 二分查找寻找峰值int left = 1;int right = arr.length-2;while (left < right) {int mid = left + (right - left + 1) / 2;// 峰值存在于左边区间,因此只能和左边区间进行比较,而不能跑到右边区间去if (arr[mid-1] < arr[mid]) {// 落在左边区域left = mid;} else {// 落在右边区域right = mid-1;}}return left;}
}

注意:

1、由于题目说了,数组长度是大于等于3并且一定存在峰值的,因此第一个元素和最后一个元素肯定不是峰值。

2、在比较时,一定要清楚我们是将峰值分在哪个区域,继而再进行正确的分值(left、right、mid)和比较。 

162. 寻找峰值

题目:

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1:

输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5 
解释:你的函数可以返回索引 1,其峰值元素为 2;或者返回索引 5, 其峰值元素为 6。

提示:

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • 对于所有有效的 i 都有 nums[i] != nums[i + 1]

思路:题目让我们随机找到一个严格大于左右两边的峰值元素即可。暴力枚举的做法也是很轻易能够想到的。

代码实现:

暴力枚举:

class Solution {public int findPeakElement(int[] nums) {// 找到严格大于左右元素即可int max = -1;for (int i = 0; i < nums.length; i++) {if (i-1 < 0) { // 只需判断右边的if (i+1 >= nums.length) {max = 0; // 当只有一个元素时break;} else {if (nums[i] > nums[i+1]) {max = i;break;}}} else { // 只需判断右边if (i+1 >= nums.length) {// 判断左边if (nums[i-1] < nums[i]) {max = i;break;}} else {// 判断两边if (nums[i] > nums[i-1] && nums[i] > nums[i+1]) {max = i;break;}}}}return max;}
}

由于题目只需要让我们随机返回一个峰值即可,因此只要是找到符合要求的就不需要再遍历数组了。

由于题目要求我们应使用时间复杂度为log N的算法来解决,因此这里我们联想到二分查找算法。

那有小伙伴可能会有疑惑:二分查找不是只适用于有序的数据的情况下吗? 

认识二分查找算法的二段性:
1、有一个条件将数组可以分成两部分。
例如:在一个有序数组中查找某个元素是否存在。
1  2  3  4  5  6  7  8
找到中间值mid,将数组分成两部分:一部分全部大于等于mid,一部分全部小于mid。
这里就是利用一个条件将数组分成了两部分。
而在本题中:找到中间值mid,根据-∞到mid和mid+1的特性(下面的图片所示),将数组分为两部分:
一部分,肯定存在峰值;一部分,可能存在峰值。 ----> 二段性。

2、确定二分查找的中间值取法、left与right的取法(可以去看第一篇关于二分查找的博客)

因此,我们确定一个题目是否可以使用二分查找算法来解决的前提是:我们可以找到一个条件,将数组划分为两部分,即确定数组是否存在二段性。而这个二段性则是最难发现的。

代码实现:

class Solution {public int findPeakElement(int[] nums) {int left = 0;int right = nums.length-1;while (left < right) {int mid = left + (right-left) / 2;if (nums[mid] > nums[mid+1]) {right = mid;} else {left = mid+1;}}return left; // 也可以是right}
}

当然上面是拿 mid 和 mid+1进行比较,也可以拿 mid-1 和 mid 进行比较

class Solution {public int findPeakElement(int[] nums) {int left = 0;int right = nums.length-1;while (left < right) {int mid = left + (right-left+1) / 2;if (nums[mid-1] < nums[mid]) {left = mid;} else {right = mid-1;}}return left; // 也可以是right}
}

代码总体实现的功能是一样的,只是细节的处理和站的角度不同而已。

这里我们看出,二分查找重在思想(怎么找到二段性),代码的实现是非常简单的。 并且我们也知道了二分查找并不是只适用于有序的数据了。

153. 寻找旋转排序数组中的最小值

题目:

已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:

  • 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 3 次得到输入数组。

示例 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

提示:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组,并进行了 1 至 n 次旋转

思路:题目罗里吧嗦地说了一大推其实就是在一个旋转数组中求最小值的问题。直接遍历即可。

代码实现:

暴力枚举:

class Solution {public int findMin(int[] nums) {int min = nums[0];for (int i = 1; i < nums.length; i++) {if (nums[i] < min) {min = nums[i];}}return min;}
}

这个暴力枚举,简直就是初学C语言的语法题,不能算是算法题。

根据题目所说的 log N 的时间复杂度,就应该联想到使用二分查找的思路。

1、选择 nums.length-1当作区分标准:

class Solution {   public int findMin(int[] nums) {int left = 0;int right = nums.length-1;// 选择nums.length-1当作标准int target = nums[nums.length-1];while (left < right) {int mid = left + (right-left) / 2;if (nums[mid] > target) {left = mid+1;} else {right = mid;}}return nums[left];}
}

2、选择 0 当作区分标准:

class Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length-1;// 选择0当作标准int target = nums[0];while (left < right) { // 这个只适合有断层的数据int mid = left + (right-left) / 2;if (nums[mid] >= target) {left = mid+1;} else {right = mid;}}// 当数组本身是有序时,上面的方法不适合。得特判一下return nums[left] > nums[0] ? nums[0] : nums[left];}
}

LCR. 173.点名

题目:

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席,请返回他的学号。

示例 1:

输入: records = [0,1,2,3,5]
输出: 4

示例 2:

输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7

提示:

1 <= records.length <= 10000

思路:

总共有五种解法:

1、哈希表

用一个数组模拟哈希表去记录 records 数组中的元素,接着再遍历哈希表,找出其中值为0的下标

代码实现:

class Solution {// 哈希表public int takeAttendance(int[] records) {int n = records.length;int[] hash = new int[n+1]; // 要多申请一个空间for (int i = 0; i < records.length; i++) {hash[records[i]]++;}// 值为0的就是丢失的数字int num = 0;// 这里要遍历哈希表for (int i = 0; i < hash.length; i++) {if (hash[i] == 0) { num = i;}}return num;}
}

2、位运算

利用异或运算符的特性(相同的数异或为0)去查找丢失的数字。

代码实现:

class Solution {// 位运算public int takeAttendance(int[] records) {int n = records.length;int num = 0;for (int i = 0; i < n; i++) {num ^= (records[i] ^ i);}return num ^ n;}
}

3、直接遍历查找

直接遍历数组,查找丢失的数字

代码实现:

class Solution {// 直接遍历查找public int takeAttendance3(int[] records) {int n = records.length;int num = -1; // 取0可能会误判for (int i = 0; i < n; i++) {if (records[i] != i) {num = i;break;}}// 排除特殊情况return num == -1 ? n : num;}
}

注意:

1、当数组处于 [0,1,2,3,4] 这种有序的状态时, 缺少的 n 是循环查找不出来的,因此得去进行特殊处理。

2、当数组处于 [1,2,3,4] 这种状态时,如果 num 初始化为 0,那么更新之后的结果还是 0,容易和上面一种情况混淆,因此 num 的初始值只能是负数。

4、数学方法(高斯求和、等差数列的求和)

将数组的值全部加起来再减去对应的下标,最后再加上数组的长度,得到的就是丢失的数字

代码实现:

class Solution {// 高斯求和public int takeAttendance(int[] records) {int sum = 0;int i = 0;for (; i < records.length; i++) {sum += (i-records[i]);}sum += i;return sum;}
}

上面方法都可以通过题目测试,但是时间复杂度还是不少的,不是最优解法。 

5、二分查找

在直接遍历查找的过程中,是直接去从头开始遍历,会将一些无效的数据也查找一遍。因此可以尝试用二分查找来优化。首先,二分查找得找到数据的二段性。

代码实现:

class Solution {// 二分查找public int takeAttendance(int[] records) {int left = 0;int right = records.length-1;while (left < right) {int mid = left + (right-left) / 2;if (records[mid] == mid) {left = mid+1;} else {right = mid;}}// 也要特判return left == records[left] ? left+1 : left;}
}

注意:因为二分查找 是对 暴力枚举的优化,因此也要避免 有序数组的情况。(二分查找只是优化在查找效率上面,其余的和暴力枚举没啥区别)

以上就是 关于二分查找的 经典题目集合了,相信通过这篇文章,咱们以后遇到二分的题目,肯定能AC的(但首先得找到二段性,这个过程是比较难的)。

好啦!本期 二分查找算法专题(2)的学习之旅 就到此结束啦!我们下一期再一起学习吧!

相关文章:

二分查找算法专题(2)

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a; 优选算法专题 对于二分查找算法不是很了解或者只了解一部分的小伙伴一定要去看下面这篇博客&#xff1a;二分查找算法的介绍与另外一种查找方…...

[Python] 编程入门:理解变量类型

文章目录 [toc] 整数常见操作 浮点数字符串字符串中混用引号问题字符串长度计算字符串拼接 布尔类型动态类型特性类型转换结语 收录专栏&#xff1a;[Python] 在编程中&#xff0c;变量是用于存储数据的容器&#xff0c;而不同的变量类型则用来存储不同种类的数据。Python 与 C…...

C(九)while循环 --- 军训匕首操情景

匕首操&#xff0c;oi~oi~oi~~~~~ 接下来的几篇推文&#xff0c;杰哥记录的是三大循环结构的运行流程及其变式。 本篇的主角是while循环。&#x1f449; 目录&#xff1a; while循环 的组成、运行流程及其变式关键字break 和 continue 在while 循环中的作用while 循环的嵌套题目…...

C#秒如何转为时分秒格式

将秒数转换为分钟和秒数可以通过简单的数学运算来实现。假设你有一个整数表示秒数,可以通过以下方式转换为分钟: 将秒数除以 3600 来获取时钟的整数部分。 将秒数求余 3600的结果除以60 来获取分钟的整数部分。 用秒数求余 60 来获取余下的秒数。 具体实现函数如下: //…...

重学SpringBoot3-集成Redis(三)

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-集成Redis&#xff08;三&#xff09; 1. 引入 Redis 依赖2. 配置 RedisCacheManager 及自定义过期策略2.1 示例代码&#xff1a;自定义过期策略 3. 配置…...

【Spine】引入PhotoshopToSpine脚本

引入 右键Photoshop图标&#xff0c;选择属性 打开文件所在位置 找到目录下的\Presets\Scripts文件夹。 找到Spine目录下的\scripts\photoshop文件夹下的PhotoshopToSpine.jsx 复制它&#xff0c;丢到Photoshop刚才找的那个目录下。 使用 打开.psd文件&#xff0c;检查不要…...

【Linux】详解Linux下的工具(内含yum指令和vim指令)

文章目录 前言1. Linux下软件安装的方式2. yum2.1 软件下载的小知识2.2 在自己的Linux系统下验证yum源的存在2.3 利用yum指令下载软件2.4 拓展yum源&#xff08;针对于虚拟机用户&#xff09; 3. vim编辑器3.1 vim是什么&#xff1f;3.2 如何打开vim3.2 vim各模式下的讲解3.2.1…...

MacBook 使用 brew 安装 MySQL

目录 &#xff08;1&#xff09;准备工作1.1 更新 brew &#xff08;2&#xff09;正式安装2.1 安装MySQL&#xff1a;2.2 启动mysql &#xff08;3&#xff09;初始化数据库3.1 选择验证密码组件3.2 密码强度3.3 删除匿名用户3.4 禁用root用户远程连接3.5 删除test数据库3.6 重…...

java中有两个list列表,尽量少的去循环

java中有两个list列表&#xff0c;一个list列表是paymentRecord&#xff0c;另外一个list是listApplyBase&#xff0c;paymentRecord中的lendCode字段值跟listApplyBase中的repaymentCode字段值是对应的&#xff0c;用stream流去循环paymentRecord列表&#xff0c;然后判断当pa…...

Java中的状态机实现:使用Spring State Machine管理复杂状态流转

在软件开发中&#xff0c;我们经常会遇到需要处理各种状态以及状态之间转换的场景。这些状态转换有时会变得非常复杂&#xff0c;特别是当涉及到多个状态&#xff0c;并且每个状态都有多个可能的触发事件导致不同的状态变化时。手动编写这样的逻辑不仅容易出错&#xff0c;而且…...

[Notes] Computer Network - Overwiew

What is the Internet? The Internet is a global network of interconnected computers that communicate using standard protocols (rules). It’s not a single entity but a network of networks that allows millions of devices worldwide to exchange data. In simp…...

MyBatisPlus——学习笔记

MyBatisPlus 一、导入依赖 <!-- MyBatisPlus --><dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.5.2</version></dependency><!-- MySql --><de…...

运维自动化shell脚本总结

运维自动化是提升IT管理效率的关键&#xff0c;使用Shell脚本可以有效地实现许多日常任务的自动化。以下是一些常见的Shell脚本应用及其总结&#xff0c;涵盖基本概念、实用示例和最佳实践。 1. Shell脚本基础 1.1 Shell脚本定义 Shell脚本是一系列命令的集合&#xff0c;通…...

前端学习第三天笔记 JavaScript JavaScript的引入 数据类型 运算符 条件语句 字符串

这里写自定义目录标题 JavaScriptJavaScript引入到文件嵌入到HTML文件中引入本地独立js文件引入网络来源文件 JavaScript的注释方式嵌入在HTML文件中的注释JavaScript的输出方式数据类型原始类型&#xff08;基础类型&#xff09;合成类型&#xff08;复合类型&#xff09; 运算…...

C++教程一口气讲完!(万字讲解)( ̄y▽ ̄)╭ Ohohoho... 下

C 常量 常量是固定值&#xff0c;在程序执行期间不会改变。这些固定的值&#xff0c;又叫做字面量。 常量可以是任何的基本数据类型&#xff0c;可分为整型数字、浮点数字、字符、字符串和布尔值。 常量就像是常规的变量&#xff0c;只不过常量的值在定义后不能进行修改。 …...

unity软件安装教程

目录 一、Unity Hub的安装 二、Unity Hub的基础设置 语言切换 安装默认路径 安装unity编辑器和visual Studio 申请许可证 创建新项目 Unity和Visual Studio进行绑定 一、Unity Hub的安装 打开浏览器输入以下网址&#xff1a;unity.cn&#xff0c;打开unity官网 点击下载&#x…...

[大语言模型-论文精读] 更大且更可指导的语言模型变得不那么可靠

[大语言模型-论文精读] 更大且更可指导的语言模型变得不那么可靠 目录 文章目录 [大语言模型-论文精读] 更大且更可指导的语言模型变得不那么可靠目录0. 摘要1. 核心内容3. 创新点4. 算法模型5. 实验效果6. 重要数据与实验结论7. 推荐阅读指数&#xff1a;8. 推荐理由 后记 论文…...

云手机可以解决TikTok运营的哪些问题?

随着社交媒体的飞速发展&#xff0c;TikTok迅速崛起&#xff0c;成为个人和企业进行品牌宣传和内容创作的首选平台。然而&#xff0c;在运营TikTok账号的过程中&#xff0c;不少用户会遇到各种问题。本文将详细阐述云手机如何帮助解决这些问题。 1. 多账号管理的高效便捷 通过云…...

Redis基础三(redis的高级配置)

Redis进阶配置 一、Redis持久化操作 ​ 持久化就是把内存的数据写到磁盘中去&#xff0c;防止服务宕机了内存数据丢失。&#xff08;Redis 数据都放在内存中。如果机器挂掉&#xff0c;内存的数据就不存在。所以需要做持久化&#xff0c;将内存中的数据保存在磁盘&#xff0c…...

Telnet、SSH、RDP和VNC

Telnet、SSH、RDP和VNC都是远程访问和管理的协议或工具&#xff0c;它们各自具有不同的特点和适用场景。 一、基本概念与用途 Telnet 定义&#xff1a;一种基于命令行界面的远程管理协议&#xff0c;允许用户通过网络远程访问和管理计算机。用途&#xff1a;主要用于远程登录和…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...