icp备案网站信息修改,网站建设面试题,wordpress按作者分类,扁平化风格网站模板峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums#xff0c;找到峰值元素并返回其索引。数组可能包含多个峰值#xff0c;在这种情况下#xff0c;返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] nums[n] -∞ 。
你必须实现时间复杂度为 O(…峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 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]
思路寻找峰值最大值就一定是峰值但这样遍历是行不通的复杂度就到了O(n)所以每次操作必须寻找减小范围的方法其核心就是找到规律该题必有峰值因为边界是无限小而且一个节点左右节点都是不相同的一个节点的峰值情况无非三种情况左小右小那么该值就是峰值左小右大那么峰值必在右边因为有上升就必然会下降最坏情况就是到边界下降到无穷小。所以按此规律可以直接进行范围缩小。代码如下和基本二分类似。
class Solution {public int findPeakElement(int[] nums) {// 由于数组边界是无穷小所以一个元素i如果i大于两侧那么他就是峰值// 如果右侧大于i右侧就必有峰值左侧同理这种情况就可以使用二分思想int leftIndex 0;int rightIndex nums.length - 1;while (true) {int middleIndex (leftIndex rightIndex) / 2;if (compare(nums, middleIndex, middleIndex-1) compare(nums, middleIndex, middleIndex1)) {return middleIndex; } else if (nums[middleIndex1] nums[middleIndex]) {leftIndex middleIndex 1;} else {rightIndex middleIndex - 1;}}}// 由于数据中可能会有int的最小值所以必须写比较函数public boolean compare(int[] nums, int index1, int index2) {if (index1 0 || index1 nums.length) {return false;}if (index2 0 || index2 nums.length) {return true;}return getNum(index1, nums) getNum(index2, nums);}public int getNum(int index, int[] nums) {return nums[index];}
}
