【LeetCode】162-寻找峰值
2024-09-01 07:01:16
题目描述
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums
,其中 nums[i] ≠ nums[i+1]
,找到峰值元素并返回其索引。
数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[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。
说明:
你的解法应该是 O(logN) 时间复杂度的。
解题思路
从说明来看,要求时间复杂度是 O(logN) ,这就几乎摆明了要用二分搜索了。
但是常规的二分搜索是要搜索一个特定的,具体的元素在集合中的位置,在这一题中要找的元素并不是一个具体的值,而是一个具有某种特征(峰值)的值,如何将二分法转换一下运用到这里呢?
与传统的二分搜索设置一个mid
指针不同的是,我们设置两个,mid1
和mid2
,来保证边界的外侧总是小于边界的,这样通过边界更新,我们可以保证递归/迭代会在局部峰值处结束。
Java 实现
递归实现
public int findPeakElement (int[] nums) {
return helper(nums, 0, nums.length - 1);
}
private int helper (int[] nums, int lo, int hi) {
if (lo == hi) {
return lo;
} else {
int mid1 = (lo + hi) / 2;
int mid2 = mid1 + 1;
if (nums[mid1] > nums[mid2]) {
return helper(nums, lo, mid1);
} else {
return helper(nums, mid2, hi);
}
}
}
迭代实现
public int findPeakElement (int[] nums) {
return helper(nums, 0, nums.length - 1);
}
private int helper (int[] nums, int lo, int hi) {
while (lo < hi) {
int mid1 = (lo + hi) / 2;
int mid2 = mid1 + 1;
if (nums[mid1] < nums[mid2]) {
lo = mid2;
} else {
hi = mid1;
}
}
return lo;
}
心得体会
二分搜索是根据mid1
,mid2
的关系对搜索区域进行调整的,确保边界外侧小于边界,从而确保最后在局部峰值处结束递归/迭代。
最新文章
- Linux 解决数量庞大wildfly容器启动与停止的脚本
- SQL Server调优系列基础篇(并行运算总结)
- 关于Html编码问题,例如字符:&;#183;
- 红黑树(二)之 C语言的实现
- iOS开发之网络编程--2、NSURLSessionDownloadTask文件下载
- JFreeChart 图表生成实例(饼图、柱状图、折线图、时序图)
- 从零开始学ios开发(十七):Storyboards(上)
- ThinkSNS积分商城系统功能详解!
- Cocos2D v3.4.9粒子效果不能显示的原因分析及解决办法
- 【原】无脑操作:Windows下搭建Kafka运行环境
- 【抱怨文】vscode对多项目支持不够友好
- tf.contrib.slim
- RAS非对称加密与数字证书数字签名
- django ORM的总结
- [3] 注解(Annotation)-- 深入理解Java:注解(Annotation)--注解处理器
- JAVA中对List<;map<;String,Object>;>;根据map某个key值进行排序
- Jmeter新手频犯错误之一(登录)
- jenkins结合脚本实现代码自动化部署及一键回滚至上一版本
- win7 键盘
- 深入浅出 Java Concurrency (6): 锁机制 part 1 Lock与ReentrantLock