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

求局部最小值

局部最小值
题目:给定一个数组,每两个相邻的数组不等,找到该数组上任意一个局部最小值。
定义:nums[1] > nums[0]
nums[len(nums) - 2] > nums[len(nums) - 1]
nums[n-1] > nums[n] && nums[n] < nums[n+1]

题目解析

通过上面的定义已知三种情况

  1. 第一个数小于第二个数
  2. 最后一个数小于倒数第二个数
    3.左右两边的数都比中间这个数大
    第一种和第二种很好判断,关键在于第三种情况。如果出现第三种情况说明不符合第一种和第二种情况。也就是说nums[1] < nums[0] 和nums[n-1] < nums[n] && nums[n] > nums[n+1].
    第一个数比第二个数大,说明他是向下的趋势。最后一个比倒数第二个大,说明是向上的趋势。那么先向下再向上必然存在局部最小值。
    画图解析:
    IMG_0038
    必然存在局部最小值。
# 求局部最小值
def part_most_min(nums):if nums is None or len(nums) == 0:return -1if len(nums) == 1:return 0# 检查左边界if nums[0] < nums[1]:return 0# 检查右边界if nums[-1] < nums[-2]:return len(nums) - 1left, right = 1, len(nums) - 2while left <= right:mid = left + (right - left) // 2# 如果中间元素比两边都小,就是局部最小值if nums[mid] < nums[mid - 1] and nums[mid] < nums[mid + 1]:return mid# 如果中间元素比左边大,局部最小值在左边elif nums[mid] > nums[mid - 1]:right = mid - 1# 如果中间元素比右边大,局部最小值在右边else:left = mid + 1return left
http://www.hskmm.com/?act=detail&tid=20956

相关文章:

  • Element-UI的transfer穿梭框组件数据量大解决方案
  • 第9章 day09 hook插件
  • nginx 一致性hash和流量检查模块
  • 深入解析:10月底实习准备-Mysql(按面试频率准备)
  • 机器学习概述 - -一叶知秋
  • CEXE的%你赛5-题解
  • C++语言(1)
  • Windows多人共享文件夹全流程,附2025新共享文件快90%
  • 第11章 day11-day12关于json请求体/逆向爬虫实战
  • 容斥与二项式反演
  • react useCallback Hook详解
  • 从Docker构建失败到CRA被淘汰:一个React项目的ES模块探索记录
  • 充气泵PCBA方案中数字传感器和模拟传感器的差异
  • 实用指南:小米17手机的上市公司供应商
  • CDN + WAF + CLB + Higress 架构下的 TLS 加解密详细解析(适用阿里云)
  • react useMemo Hook详解
  • react useContext 详解
  • Python技能大赛-备赛建议
  • 【软件系统架构】系列七:系统性能——操作系统性能深入解析 - 实践
  • 你的下一款定位神器,何必是GPS?Nordic带你解锁Wi-Fi SSID的隐藏潜能
  • CF407E k-d-sequence 题目分析(0929模拟赛最后一题)
  • Linux 生成随机端口
  • MATLAB 中 dsp.FFT 系统对象:从原理到实践的完整指南
  • 并发编程可见性
  • C# Devexpress GridControl实现全选功能(转载,记录)
  • github Connection reset by 20.205.243.160 port 443 fatal: Could not read from remote repository.
  • VsCode Ai插件
  • 完整教程:基于完全分布式模式部署Hadoop(喂饭教程)
  • Vue 3.6 引入 Vapor Mode,虚拟DOM已死?
  • part 10