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

C++二分算法的应用:寻找峰值原理、源码及测试用例

 说明

此文是课程https://edu.csdn.net/course/detail/38771 的讲义。

源码下载:https://download.csdn.net/download/he_zhidan/88458478

题目

长度为n的数组nums,请返回任意一峰值的索引。符合以下条件之一i便是峰值的索引。

n等于1

i等于0

n>1

i等于0

nums[i] >nums[i+1]

n>1

i等于n-1

nums[i] > nums[i-1]

0<i<n-1

nums[i]>nums[i-1]

nums[i]>nums[i+1]

题目保证nums[i]不等于nums[i+1]。

分析

假定

nums[left,r)符合nums[left]>nums[left-1],且nums[r-1]>nums[r]。显然初始情况nums[0,n)符合。

推论一:如果[left,r)的长度为1,则left就是返回的索引。

推论二:假定left < mid<r。如果mid[mid] > mid[mid-1],则nums[mid,r)也符合假定。如果mid[mid] < mid[mid-1],则nums[left,mid)也符合假定。

推论三:推论二也可以也可以理解成分别抛弃[left,mid)和[mid,r)。令mid = left+(r-left)/2,由于r-left>=2,所以left<mid<r。也就是抛弃的子数组不会为空。也就是数组不断变短。等长度为1结束。

时间复杂度

由于每次抛弃一半,所以需要抛弃logn次。故时间复杂度O(logn)

核心代码

class Solution {

public:

    int findPeakElement(vector<int>& nums) {

        int left = 0, r = nums.size();

        while (r - left > 1)

        {

            const int mid = left + (r - left) / 2;

            if (nums[mid] > nums[mid - 1])

            {

                left = mid;

            }

            else

            {

                r = mid;

            }

        }

        return left;

    }

};

测试用例

int main()

{

    Solution slu;

    vector<int> nums = { 1,2,3,4 };

    int res = slu.findPeakElement(nums);

    assert(3 == res);

    nums = { 4,3,2,1 };

    res = slu.findPeakElement(nums);

    assert(0 == res);

    nums = { 2,5,3,1 };

     res = slu.findPeakElement(nums);

    assert(1 == res);

}

https://img-blog.csdnimg.cn/ea2601b3918f4aef836b5fe30da2ebf7.gif#pic_center#pic_center

其它

学院课程

基础算法的C++实现课程,请点击下面的CSDN学院的链接。

2024年1月15之前完全免费,之后绝大部分免费

https://edu.csdn.net/course/detail/38771

C#入职培训

此课程的目的:让新同事更快完成从学生到C#程序员的转换,更快上手完成C#的开发工作。

https://edu.csdn.net/course/detail/38768

C++入职培训

让新同事更快完成从学生到C++程序员的转换,更快上手完成C++的开发工作。

https://edu.csdn.net/course/detail/32049

运行验证环境

Win10 VS2022 Ck++17 或win7 VS2019 C++17

每天都补充正能量

好好学习,天天向上。

事无终始,无务多业。

是故置本不安者,无务丰末。

相关下载

如果你时间宝贵,只想看精华,请到CSDN下载频道下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

https://img-blog.csdnimg.cn/f95ddae62a4e43a68295601c723f92fb.gif#pic_center

相关文章:

C++二分算法的应用:寻找峰值原理、源码及测试用例

说明 此文是课程https://edu.csdn.net/course/detail/38771 的讲义。 源码下载&#xff1a;https://download.csdn.net/download/he_zhidan/88458478 题目 长度为n的数组nums&#xff0c;请返回任意一峰值的索引。符合以下条件之一i便是峰值的索引。 n等于1 i等于0 n>…...

外汇天眼:本周无牌裸奔平台名单出炉,你踩“坑”了么?!!

监管信息早知道&#xff01;外汇天眼将每周定期公布监管牌照状态发生变化的交易商&#xff0c;以供投资者参考&#xff0c;规避投资风险。如果平台天眼评分过高&#xff0c;建议投资者谨慎选择&#xff0c;因为在外汇天眼评分高不代表平台没问题&#xff01; 以下是监管牌照发生…...

10 读写锁ReentrantReadWriteLock

1 介绍 为什么要使用读写锁&#xff1f; 需要高并发读取和较低并发写入的应用程序&#xff0c;降低锁的粒度&#xff0c;提高系统性能 使用场景&#xff1a; 读多写少的共享资源 缓存管理&#xff1a;读 >> 写&#xff0c;控制多个线程同时读缓存&#xff0c;需要刷新o…...

laravel队列

laravel redis队列 1、创建job队列任务 php artisan make:job StoreUser执行上述命令后&#xff0c;会生成app/Jobs/StoreUser.php文件&#xff0c;编辑文件内容如下&#xff1a; <?phpnamespace App\Jobs;use Illuminate\Bus\Queueable; use Illuminate\Contracts\Queu…...

【计算机网络】TCP 协议的相关特性

TCP&#xff08;传输控制协议&#xff09;是一种面向连接的、可靠的、基于字节流的协议。以下是TCP协议的相关特性&#xff1a; 可靠性&#xff1a;TCP通过确认和重传机制保证数据的可靠传输。 面向连接&#xff1a;TCP在传输数据前需要先建立连接。连接的建立过程包括三次握手…...

[软件安装] tmux安装及相关事项

tmux安装及相关事项 tmux是一个终端复用工具&#xff0c;可以在单个终端窗口中同时运行多个终端会话。安装tmux可以提高工作效率&#xff0c;使命令行操作更加方便。 1. 安装tmux&#xff1a; 在Linux系统下&#xff0c;可以使用包管理器来安装tmux&#xff0c;比如在Ubuntu…...

leetcode 887 ——扔鸡蛋

题目大意&#xff1a; 你有k个鸡蛋&#xff0c;对n层楼的建筑&#xff0c;请确认在f层扔鸡蛋鸡蛋恰好不会破碎的最少次数&#xff08;f满足 0 < f < n&#xff09;。 方法一&#xff1a; 状态&#xff1a;即会发生变化的量&#xff0c;很明显有两个&#xff0c;当前拥有…...

自动化运维ansible(role)

一、role的介绍 1、Roles称为角色&#xff0c;本质上是为简化playbook配置文件而产生的一种特殊的方法。 2、简单来说&#xff0c;roles就是将原本在一个yaml中的文件进行规则化分散&#xff0c;封装到不同的目录下&#xff0c;从而简化playbook的yaml配置文件大小。从其实现方…...

linux命令笔记

创建文件夹 sudo mkdir 文件夹名vim笔记 vim的查找和退出查找 进入vim 按/ 输入内容即可查找 按enter结束查找vim创建文件并在里面写东西 比如创建文件为 hello.cpp vim hello.cpp查看所有文件 # 查看所有文件&#xff0c;并以列表的形式查看&#xff0c;显示出文件大小 …...

2.3.C++项目:网络版五子棋对战之实用工具类模块的设计

文章目录 一、实用工具类模块&#xff08;一&#xff09;功能 二、设计和封装&#xff08;一&#xff09;日志宏封装&#xff08;二&#xff09;mysql_util封装&#xff08;三&#xff09;Jsoncpp-API封装&#xff08;四&#xff09;file_util封装&#xff08;五&#xff09;st…...

跳跃游戏----题解报告

题目&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题解&#xff1a; 其实就直接挨着跳就行了&#xff0c;循环中不断更新k&#xff0c;不停比较k和当前位置跳跃的最大值即可 代码&#xff1a; public boolean canJump(int[] nums) …...

SpringBoot下的代理注解

EnableAspectJAutoProxy Target(ElementType.TYPE) Retention(RetentionPolicy.RUNTIME) Documented Import(AspectJAutoProxyRegistrar.class) public interface EnableAspectJAutoProxy {// 是否代理目标对象&#xff0c;ture:使用CGLIB代理 fasle:使用JDK代理boolean proxy…...

[C++随想录] 二叉搜索树

搜素二叉树 二叉搜索树的使用二叉搜索树的模拟实现(K)整体结构循环版本递归版本 二叉搜索树的应用源码(kv) 二叉搜索树的使用 二叉搜索树 相较于 普通的二叉树来说: 根节点的左子树的所有键值都 小于 根节点, 根节点的右子树的所有键值 大于 根节点根节点的 左右子树 都是 二…...

Windows Server 2019 搭建FTP站点

目录 1.添加IIS及FTP服务角色 2.创建FTP账户&#xff08;用户名和密码&#xff09;和组 3.设置共享文件夹的权限 4.添加及设置FTP站点 5.配置FTP防火墙支持 6.配置安全组策略 7.客户端测试 踩过的坑说明&#xff1a; 1.添加IIS及FTP服务角色 a.选择【开始】→【服务器…...

Ubuntu 22.04 中安装 fcitx5

Ubuntu 22.04 中安装 fcitx5 可以按照以下步骤进行&#xff1a; 添加 fcitx5 的 PPA 首先&#xff0c;添加 fcitx5 的官方 PPA&#xff1a; sudo add-apt-repository ppa:fcitx-team/fcitx5更新软件包列表 sudo apt update安装 fcitx5 sudo apt install fcitx5 fcitx5-conf…...

CleanMyMac X免费macOS清理系统管家

近些年伴随着苹果生态的蓬勃发展&#xff0c;越来越多的用户开始尝试接触Mac电脑。然而很多人上手Mac后会发现&#xff0c;它的使用逻辑与Windows存在很多不同&#xff0c;而且随着使用时间的增加&#xff0c;一些奇奇怪怪的文件也会占据有限的磁盘空间&#xff0c;进而影响使用…...

CVer从0入门NLP(一)———词向量与RNN模型

&#x1f34a;作者简介&#xff1a;秃头小苏&#xff0c;致力于用最通俗的语言描述问题 &#x1f34a;专栏推荐&#xff1a;深度学习网络原理与实战 &#x1f34a;近期目标&#xff1a;写好专栏的每一篇文章 &#x1f34a;支持小苏&#xff1a;点赞&#x1f44d;&#x1f3fc;、…...

乐观锁和悲观锁

目录 悲观锁&#xff1a;乐观锁&#xff1a;CAS算法:版本号机制&#xff1a;write_condition 机制&#xff1a;时间戳&#xff1a;ReentrantLock 类&#xff1a; 独占锁&#xff1a;synchronized 关键字&#xff1a; 悲观锁&#xff1a; 1、理解&#xff1a;总是假设最坏的情况…...

用 pytorch 训练端对端验证码识别神经网络并进行 C++ 移植

文章目录 前言安装安装 pytorch安装 libtorch安装 opencv&#xff08;C&#xff09; 准备数据集获取训练数据下载标定 编码预分析 数据集封装格式 神经网络搭建神经网络训练神经网络测试神经网络预测C 移植模型转换通过跟踪转换为 Torch Script通过注解转换为 Torch Script 编写…...

leetcode 739. 每日温度、496. 下一个更大元素 I

739. 每日温度 给定一个整数数组 temperatures &#xff0c;表示每天的温度&#xff0c;返回一个数组 answer &#xff0c;其中 answer[i] 是指对于第 i 天&#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高&#xff0c;请在该位置用 0 来代替。 示例 1: …...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...