当前位置: 首页 > news >正文

【LeetCode刷题-二分查找】--162.寻找峰值

162.寻找峰值

image-20231112104629733

方法一:寻找最大值

题目保证了nums[i]≠nums[i+1],所以数组nums中最大值两侧的元素一定严格小于最大值本身,因此最大值所在的位置就是一个可行的峰值位置

class Solution {public int findPeakElement(int[] nums) {int idx = 0;for(int i=0;i<nums.length;i++){if(nums[i] > nums[idx]){idx = i;}}return idx;}
}

方法二:使二分查找优化迭代爬坡

image-20231112104931752

image-20231112104944213

class Solution {public int findPeakElement(int[] nums) {int n = nums.length;int left = 0,right = n - 1,ans = -1;while(left <= right){int mid = (left + right) / 2;if(compare(nums,mid - 1,mid) < 0 && compare(nums,mid,mid + 1) > 0){ans = mid;break;}if(compare(nums,mid,mid + 1)< 0){left = mid + 1;}else{right = mid -1;}}return ans;}// 辅助函数,输入下标 i,返回一个二元组 (0/1, nums[i])// 方便处理 nums[-1] 以及 nums[n] 的边界情况public int[] get(int[] nums,int idx){if(idx == -1 || idx == nums.length){return new int[]{0,0};}return new int[]{1,nums[idx]};}public int compare(int[] nums,int idx1,int idx2){int[] num1 = get(nums,idx1);int[] num2 = get(nums,idx2);if(num1[0] != num2[0]){return num1[0] > num2[0] ? 1:-1;} if(num1[1] == num2[1]){return 0;}return num1[1] > num2[1] ? 1:-1;}
}

方法三:二分查找

  • 在题目描述中出现了nums[-1]=nums[n]=-∞,就代表着只要数组中存在一个元素比相邻元素大,那么沿着它一定就可以找到一个峰值
  • 根据上述结论,可以使用二分查找找到峰值
  • 查找时,左指针l,右指针r,以其保持左右顺序为循环条件
  • 根据右指针计算中间位置m,并比较m和m+1的值,如果m较大,则左侧存在峰值,r=m,如果m+1较大,则右侧存在峰值,l=m+1
class Solution {public int findPeakElement(int[] nums) {int left = 0, right = nums.length - 1;for (; left < right; ) {int mid = left + (right - left) / 2;if (nums[mid] > nums[mid + 1]) {right = mid;} else {left = mid + 1;}}return left;}
}
http://www.lryc.cn/news/226850.html

相关文章:

  • vscode调试react 最初的源码
  • Netty网络通信模型
  • .NET快速对接极光消息推送
  • Doris:多源数据目录(Multi-Catalog)
  • 建行驻江门市分行纪检组以政治谈话压责任促发展
  • 如何从存档服务器上完全删除PDM用户
  • 导师对学生学术论文的指导包括哪些方面,请详细展开说明
  • 嵌入式软件开发是个啥职业?
  • 03【远程协作开发、TortoiseGit、IDEA绑定Git插件的使用】
  • Linux:centos7通过yum安装mysql的方法
  • 【算法与数据结构】93、LeetCode复原 IP 地址
  • uniapp点击图片放大预览
  • Java TreeMap
  • ubuntu 内网源如何搭建 —— 筑梦之路
  • 测试用例的设计方法(黑盒)
  • Shell编程入门--概念、特性、bash配置文件
  • 读书笔记:彼得·德鲁克《认识管理》第14章 工作、做工与员工
  • diffusers库中stable Diffusion模块的解析
  • 智慧城市照明为城市节能降耗提供支持继电器开关钡铼S270
  • 固高GTS800控制卡开发数控系统宏程序心得
  • linux入门---线程池的模拟实现
  • jQuery HTML/CSS 参考文档
  • QT 布局管理综合实例
  • 使用 pubsub-js 进行消息发布订阅
  • TA Shader基础
  • VScode + opencv(cmake编译) + c++ + win配置教程
  • Vue中的常用指令v-html / v-show / v-if / v-else / v-on / v-bind / v-for / v-model
  • ChatGPT 提问技巧
  • 2023-11-09 LeetCode每日一题(逃离火灾)
  • 阿里云-maven私服idea访问私服与组件上传