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

yipeiwu_com7年前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设计】。

相关文章

Flask和Django框架中自定义模型类的表名、父类相关问题分析

本文实例分析了Flask和Django框架中自定义模型类的表名、父类相关问题。分享给大家供大家参考,具体如下: 一. Flask和Django中定义表名(执行迁移后生成)的方式和flas...

python获取各操作系统硬件信息的方法

本文实例讲述了python获取各操作系统硬件信息的方法。分享给大家供大家参考。具体如下: 1. windows 使用WMI: (WMI官网地址:http://pypi.python.or...

python中pandas.DataFrame对行与列求和及添加新行与列示例

本文介绍的是python中pandas.DataFrame对行与列求和及添加新行与列的相关资料,下面话不多说,来看看详细的介绍吧。 方法如下: 导入模块: from pandas i...

状态机的概念和在Python下使用状态机的教程

什么是状态机? 关于状态机的一个极度确切的描述是它是一个有向图形,由一组节点和一组相应的转移函数组成。状态机通过响应一系列事件而“运行”。每个事件都在属于“当前”节点的转移函数的控制范围...

python检查URL是否正常访问的小技巧

python检查URL是否正常访问的小技巧

今天,项目经理问我一个问题,问我这里有2000个URL要检查是否能正常打开,其实我是拒绝的,我知道因为要写代码了,正好学了点Python,一想,python处理起来容易,就选了pytho...