leetcode162. 寻找峰值 变种二分见过吗
二分 寻找 变种 峰值
2023-09-27 14:25:55 时间
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 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) 时间复杂度的。
思路:
二分,具体见代码。(一直保持夹逼的趋势,搜出一个数字即可)
public class Solution {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1])
r = mid;
else
l = mid + 1;
}
return l;
}
}
相关文章
- Kafka竟然也用二分搜索算法查找索引!
- 【二分查找】详细图解——助你破剑指offer经典例题
- 【LeetCode】搜索旋转排序数组 [M](二分)
- 二分搜索插入
- poj 3897 Maze Stretching 二分+A*搜索
- php 二分查找法算法具体解释
- Python 二分查找
- LeetCode_二分搜索_中等_436.寻找右区间
- LeetCode_双指针_二分搜索_简单_392.判断子序列
- LeetCode_动态规划_二分搜索_耐心排序_中等_300.最长递增子序列
- 【jzoj 3515】软件公司(DP)(二分)
- 【luogu P7518】宝石(主席树)(二分)
- 【ybt金牌导航6-6-1】区间第k小 / 整体二分例题