成都网站设计与制作,wordpress 招聘插件,广告制作平台,济宁建设信息网官网文章目录题目描述思路 代码1. 暴力法 O(n)2. 二分法 O(logN)二刷打卡第十七天#xff5e; 题目描述
难点在于 logN 复杂度
思路 代码
1. 暴力法 O(n)
最简单的做法#xff0c;直接遍历判断即可。
class Solution {public int findPeakElement(in…
文章目录题目描述思路 代码1. 暴力法 O(n)2. 二分法 O(logN)二刷打卡第十七天 题目描述
难点在于 logN 复杂度
思路 代码
1. 暴力法 O(n)
最简单的做法直接遍历判断即可。
class Solution {public int findPeakElement(int[] nums) {if(nums.length 1) {return 0;}if(nums.length 2) {return nums[1] nums[0] ? 1 : 0;}if(nums[0] nums[1]) {return 0;}if(nums[nums.length - 1] nums[nums.length - 2]) {return nums.length - 1;}// 定义值大于左右相邻值的元素for(int i 1; i nums.length - 1; i) {if(nums[i] nums[i - 1] nums[i] nums[i 1]) {return i;}}return -1;}
}2. 二分法 O(logN)
说到O(logN)的复杂度那么基本上可以直接往二分走了。注意题干中的nums[0] nums[n] -∞这是我们可以二分的基础。二分思路取mid进行nums[mid]、nums[mid 1] 对比往较大处递归。leetcode 评论区看到这个例子很便于理解爬山因为左边、右边的终点都是山底 题干-∞条件因此当前往高处走的话最终肯定能走到山峰。来个例子 图方便理解[1,2,1,3,5,6,4]注意趋势线保持左边界上升、右边界下降
class Solution {public int findPeakElement(int[] nums) {// 爬山思想两边的终点都是山底当前往高爬肯定能碰到峰顶终点要下山的嘛int left 0;int right nums.length - 1;// 先确定每次二分大的一边肯定有峰值while(left right) {int mid left (right - left) / 2;if (nums[mid] nums[mid 1]) {right mid;} else {left mid 1;}}// 循环结束后left right此时可以保证 nums[i] 是相邻的峰值return left;}
}
二刷
爬山思路可给我留下太深印象了
class Solution {public int findPeakElement(int[] nums) {// 只要在往上就一定能到顶int left 0, right nums.length - 1;while(left right){int mid (left right) / 2;if(nums[mid] nums[mid 1]) {left mid 1;} else {right mid;}}return left;}
}
