Python 求数组局部最大值的实例

yipeiwu_com6年前Python基础

求数组局部最大值

给定一个无重复元素的数组A[0…N-1],求找到一个该数组的局部最大值。规定:在数组边界外的值无穷小。即:A[0]>A[-1],A[N-1] >A[N]。

显然,遍历一遍可以找到全局最大值,而全局最大值显然是局部最大值。

可否有更快的办法?

算法描述

使用索引left、right分别指向数组首尾。

求中点 mid = ( left + right ) / 2

A[mid]>A[mid+1],丢弃后半段:right=mid

A[mid+1]>A[mid],丢弃前半段:left=mid+1

递归直至left==right

时间复杂度为O(logN)。

Python代码

def local_maximum(li):
  if li is None:
    return
  left = 0
  right = len(li) - 1
  while left < right:
    mid = int((left + right) / 2)
    if li[mid] > li[mid + 1]:
      right = mid
    else:
      left = mid + 1
  return li[left]


if __name__ == '__main__':
  li = [1, 5, 2, 3, 4, 0]
  result = local_maximum(li)
  print(result)

输出结果:4

以上这篇Python 求数组局部最大值的实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

使用python中的in ,not in来检查元素是不是在列表中的方法

使用python中的in ,not in来检查元素是不是在列表中的方法

如果在列表中返回True ,否则返回False 以上这篇使用python中的in ,not in来检查元素是不是在列表中的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希...

Python selenium 三种等待方式详解(必会)

很多人在群里问,这个下拉框定位不到、那个弹出框定位不到…各种定位不到,其实大多数情况下就是两种问题:1 有frame,2 没有加等待。殊不知,你的代码运行速度是什么量级的,而浏览器加载渲...

Python实现注册登录系统

Python实现注册登录系统

  表单在网页中主要负责数据采集功能。一个表单有三个基本组成部分: 表单标签:这里面包含了处理表单数据所用CGI程序的URL以及数据提交到服务器的方法。 表单域:包含了文本框、...

python实现根据用户输入从电影网站获取影片信息的方法

本文实例讲述了python实现根据用户输入从电影网站获取影片信息的方法。分享给大家供大家参考。具体如下: 这段python代码主要演示了用户终端输入,正则表达式,网页抓取等 #!/u...

Python将视频或者动态图gif逐帧保存为图片的方法

本文是基于opencv将视频和动态图gif保存为图像帧。可以根据输入视频格式的不同,修改第21行。        对动图的处理...