用分享的方式成长,用有趣的眼光看世界。
欢迎来到12 26 25的博客 !
热爱编码、算法、知识总结,不定期更新有趣、有料、有营养内容。 让我们共同学习,共同进步。
系列索引 : 【刷题笔记0】系列目录索引(持续更新 & 推荐收藏)
本题题目: LeetCode 162. 寻找峰值
分类:二分查找, 思维
难度: 中等
老规矩,先上AC图:
题目: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]
题解:
首先读题,题目中给到的序列是一个无需数组,同时有多个峰值,而我们只需要找到一个即可。另外丢复杂度要求是logN。
分析题意,我们不一定需要遍历所有元素,只要确定到峰值即可,同时logN第一反应就是二分(查分)法。
所以确定下来之后对于二分查找,明确两点 1. 明确终止条件 2. 确定子序列范围(边界)
1. 首先终止条件是找到波峰,返回波峰位置。那么如何确定波峰,就需要和左右两点分别进行比较。但这里有特殊情况
- 当序列(子序列)只剩一个值是什么情况?
- 注意比较时,遇到边界情况如何处理。
2. 根据当前点mid 的情况分析更大点所在区间,进而更新left和right的情况。
时间复杂度: O(logN); 空间复杂度: O(1).
代码如下:
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while(left != right){
int mid = (left + right) / 2;
if(nums[mid] > nums[mid + 1]) {
if(mid == left) return mid;
else if(nums[mid] > nums[mid - 1]) return mid;
else right = mid - 1;
}else{
left = mid + 1;
}
}
return left;
}
};
上一篇: 从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密
下一篇: 400+条实用C/C++框架、库、工具整理 ,你能想到的都在这里了
如果有什么要补充的,欢迎下方👇评论区留言~
1份赞许 = 100分的认可,如果感觉还不错,点个赞👍 支持一下吧 ~
不定期分享 有趣、有料、有营养内容,欢迎 订阅关注 🤝 我的博客 ,期待在这与你相遇 ~
本文含有隐藏内容,请 开通VIP 后查看