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

算法:852.山脉数组的峰顶索引

题目

链接:leetcode链接
在这里插入图片描述

思路分析(二分算法)

题目的提示已经非常明显了,使用O(logN)的算法,那就是二分算法。

如何寻找二段性?

观察数据,可以发现,需要找的峰顶索引的左右两侧数据有不同的特征
峰顶索引左边的数据都比前一个数据大
峰顶索引右边的数据都比前一个数据小

根据此二段性,我们就可以设计出二分算法了

细节:

  1. left < right(不用等号)
  2. mid = left + (right - left + 1) / 2 ( 寻找右边界)

代码

int peakIndexInMountainArray(vector<int>& arr) {int left = 0,right = arr.size() - 1;while(left < right){int mid = left + (right - left + 1) /2;if(arr[mid] > arr[mid - 1]) left = mid;else right = mid - 1;}return left;}

http://www.mrgr.cn/news/39212.html

相关文章:

  • Windows Defender 强力删除工具 Defender Remover 下载
  • 网络游戏通信方案概述
  • Python NumPy 标准数据生成:高效创建与操作数组
  • 泛型中的通配符<?>、<? extends T>、<? super T>的使用场景。ArrayList与LinkedList的区别及适用场景。
  • 计算机知识科普问答--22(106-110)
  • 【Android 14源码分析】Activity启动流程-2
  • LeetCode 每日一题 买票需要的时间
  • 不同的子序列
  • elastic search 后端启动成功标志(二)
  • NLP任务之预测最后一个词
  • 程序员数学 | 用递归将复杂的问题简单化(上)
  • 企业如何提升知识产权管理效率?
  • rocketmq集群模式介绍
  • 【AI大模型】Function Calling
  • Python NumPy 读取与保存数据:高效处理数据文件
  • 九块九付费进群系统 wxselect SQL注入漏洞
  • Foo a30 = Foo(123);会调用哪些构造函数
  • 第十四周学习周报
  • 先刮腻子还是先装柜子好呢?
  • 系统数据文件和信息