网站建设补贴是经信局的政策吗,有域名如何建网站,工程项目编号查询系统,制作网站专业公司哪家好解法都在代码里#xff0c;不懂就留言或者私信
想清楚的话会特别简单#xff0c;你可能想不到这是个二分。。。
class Solution {/**本题题目规定我们只能用O(logN)的时间复杂度来解题#xff0c;这显然就是让二分嘛而题目给的数组本身是无需#xff0c;怎么二分呢其实我… 解法都在代码里不懂就留言或者私信
想清楚的话会特别简单你可能想不到这是个二分。。。
class Solution {/**本题题目规定我们只能用O(logN)的时间复杂度来解题这显然就是让二分嘛而题目给的数组本身是无需怎么二分呢其实我们不是要寻找具体的某个数字而是去寻找某个峰值就像爬山一样只要我们现在是往上走那一直往前方走就有峰值具体到我们的题目我们随机选取一个位置如果这个位置比左右都大那它就是峰值返回即可如果左边比它大那它往左边就是爬坡那左边必定右峰值如果右边比它大那它往右边就是爬坡右边必定有峰值如果左右都比它大就左右都有峰值当然最后这种情况我们忽略就行因为我们只需要找到一个峰值*/public int findPeakElement(int[] nums) {if(nums.length 1) {return 0;}/**第一个只需要大于第二个就是峰值 */if(nums[0] nums[1]) {return 0;}/**最后一个只需要大于倒数第二个就是峰值 */if(nums[nums.length-1] nums[nums.length - 2]) {return nums.length - 1;}/**如果第一个和最后一个都不是峰值我们从1~nums.length-2里找*/int left 1;int right nums.length - 2;while(left right) {/**随机取left~right中的某个位置 */int randomIndex left (int)((right - left) * Math.random());/**如果比左右都大那不就是我们的答案吗这么写不会越界吗不会因为我们是在第二个~倒数第二个之间尝试的*/if(nums[randomIndex] nums[randomIndex-1] nums[randomIndex] nums[randomIndex 1]) {return randomIndex;/**右边大右边肯定有峰值 */} else if(nums[randomIndex1] nums[randomIndex]) {left randomIndex 1;} else {/**左边大左边肯定有峰值 */right randomIndex - 1;}}return -1;}
}
