化工网站建站模板,可以做试题的网站,网站开发制作学徒,做平台的网站题目描述
峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums#xff0c;其中 nums[i] ≠ nums[i1]#xff0c;找到峰值元素并返回其索引。数组可能包含多个峰值#xff0c;在这种情况下#xff0c;返回任何一个峰值所在位置即可。你可以假设 nums[-1] nums[n…题目描述
峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums其中 nums[i] ≠ nums[i1]找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个峰值所在位置即可。你可以假设 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) 时间复杂度的。来源力扣LeetCode
链接https://leetcode-cn.com/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。方法1二分法
思路
假如存在目标值 nums[m]那么目标值需要满足的条件是
nums[m] nums[m - 1] and nums[m] nums[m 1]
剩下就是二分模板的事。
复杂度
时间复杂度$O(logn)$空间复杂度$O(1)$
代码
JavaScript Code
/*** param {number[]} nums* return {number}*/
var findPeakElement function (nums) {let l 0,m 0,r nums.length - 1;while (l r) {m Math.floor(l (r - l) / 2);if (nums[m] nums[m 1]) r m;else l m 1;}return l;
};
