网站建设到底属于什么行业,网页版wordpress教程视频,安徽建设厅网站考勤,简单网站php源码下载文章目录1 题目理解2 线性扫描3 递归二分查找1 题目理解
输入#xff1a;int[] nums并且 nums[i]!nums[i1] 输出#xff1a;找到称为峰值的那个数字#xff0c;返回其下标。 规则#xff1a;峰值是指#xff1a;nums[i-1]nums[i] 并且 nums[i1]nums[i]。你可以认…
文章目录1 题目理解2 线性扫描3 递归二分查找1 题目理解
输入int[] nums并且 nums[i]!nums[i1] 输出找到称为峰值的那个数字返回其下标。 规则峰值是指nums[i-1]nums[i] 并且 nums[i1]nums[i]。你可以认为nums[-1] nums[n] -∞.只要返回其中的一个峰值下标即可。
2 线性扫描
参考网址 我们可以利用nums[i-1]nums[i]nums[i1]nums[i]找到峰值。当我们遇到一个数字的时候只需要判断nums[i]nums[i1]即可。 为什么是这样下面分三种情况描述。
情况1所有数字以降序排列。在这种情况下第一个元素就是峰值。我们判断nums[i]nums[i1]就得出结论。当然这个时候我们不需要判断nums[i-1]与nums[i]。
情况2所有元素以上升序列排列。最后一个元素是峰值。在这种情况下我们会一直判断nums[i]与nums[i1]的关系一直不符合nums[i]nums[i1],所以选择最后一个元素为峰值。
情况3峰值处于中间某处。当遍历上升部分的时候与情况2相同没有元素满足nums[i]nums[i1]。我们不需要比较nums[i]与上一个元素nums[i-1]的关系。当达到峰值元素时候nums[i]nums[i1]满足条件不需要判断nums[i]与上一个元素nums[i-1]的关系。由于会遍历到nums[i]就已经证明了nums[i-1]nums[i]。某则就判断为峰值了。
class Solution {public int findPeakElement(int[] nums) {for(int i1;inums.length;i){if(nums[i]nums[i-1]){return i-1;}}return nums.length-1;}
}3 递归二分查找
二分法用于有序数数中。我们可以将一个普通数组看做是升序降序交替的数组。结果只要返回其中一个峰值即可。利用这两点我们可以使用二分。
如果当前处理的元素处于下降子序列那么峰值一定在这个值的左边也可能包含这个值。如果当前处理的元素处于上升子序列那么峰值一定在这个值的右边。因为比较的是nums[i]和nums[i1]的关系所以在此情况下峰值肯定不是当前元素。
class Solution {public int findPeakElement(int[] nums) {return findPeakElement(nums,0,nums.length-1);}private int findPeakElement(int[] nums,int l,int r){if(lr) return l;int m l ((r-l)1);if(nums[m]nums[m1]){return findPeakElement(nums,l,m);}else{return findPeakElement(nums,m1,r);}}
}leetcode 852和本题分析思路一样。
