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

yipeiwu_com5年前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 MySQLdb模块连接操作mysql数据库实例

mysql是一个优秀的开源数据库,它现在的应用非常的广泛,因此很有必要简单的介绍一下用python操作mysql数据库的方法。python操作数据库需要安装一个第三方的模块,在http:...

python3 实现的人人影视网站自动签到

这是一个自动化程度较高的程序,运行本程序后会从chrome中读取cookies用于登录人人影视签到, 并且会自动添加一个windows 任务计划,这个任务计划每天下午两点会执行本程序进行...

python数据持久存储 pickle模块的基本使用方法解析

python的pickle模块实现了基本的数据序列和反序列化。通过pickle模块的序列化操作我们能够将程序中运行的对象信息保存到文件中去,永久存储;通过pickle模块的反序列化操作,...

Python socket聊天脚本代码实例

这篇文章主要介绍了Python socket聊天脚本代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 没有前端,多开了一条线程用...

python+django加载静态网页模板解析

python+django加载静态网页模板解析

接着前面Django入门使用示例 今天我们来看看Django是如何加载静态html的? 我们首先来看一看什么是静态HTML,什么是动态的HTML?二者有什么区别? 静态HTML指的是使用...