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

相关文章

python判断所输入的任意一个正整数是否为素数的两种方法

素数(也称质数),是指除了1和该数本身,不能被任何正整数整除的正整数。判断一个正整数m是否为素数,只要判断m可否被2~根号m之中的任何一个正整数整除,如果m不能被此范围中任何一个正整数整...

python进阶教程之词典、字典、dict

基础教程介绍了基本概念,特别是对象和类。 进阶教程对基础教程的进一步拓展,说明Python的细节。希望在进阶教程之后,你对Python有一个更全面的认识。 之前我们说了,列表是Pytho...

在pycharm上mongodb配置及可视化设置方法

在pycharm上mongodb配置及可视化设置方法

一、mongodb安装 在官网下载适应于自己平台的mongodb,在此安装环境为Windows7-64bit 下载完成后直接安装,连续点击next选项直到,此处注意!!!!! 切勿勾...

pip 错误unused-command-line-argument-hard-error-in-future解决办法

在我的Mac Air上,用pip安装一些Python库时,偶尔就会遇到一些报错,关于“unused-command-line-argument-hard-error-in-future”...

python绘制双Y轴折线图以及单Y轴双变量柱状图的实例

python绘制双Y轴折线图以及单Y轴双变量柱状图的实例

近来实验室的师姐要发论文,由于论文交稿时间临近,有一些杂活儿需要处理,作为实验室资历最浅的一批,我这个实习生也就责无旁贷地帮忙当个下手。今天师姐派了一个小活,具体要求是: 给一些训练模型...