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使用matplotlib绘制Logistic曲线操作示例

Python使用matplotlib绘制Logistic曲线操作示例

本文实例讲述了Python使用matplotlib绘制Logistic曲线操作。分享给大家供大家参考,具体如下: 标准Logistic函数为: f(x) = 1 / ( 1 + ex...

python MysqlDb模块安装及其使用详解

python MysqlDb模块安装及其使用详解

python调用mysql数据库通常通过mysqldb模块,简单说下如何调用 1.安装驱动 目前有两个MySQL的驱动,我们可以选择其中一个进行安装: 1. MySQL-pytho...

对pandas中时间窗函数rolling的使用详解

在建模过程中,我们常常需要需要对有时间关系的数据进行整理。比如我们想要得到某一时刻过去30分钟的销量(产量,速度,消耗量等),传统方法复杂消耗资源较多,pandas提供的rolling使...

Django自定义过滤器定义与用法示例

本文实例讲述了Django自定义过滤器定义与用法。分享给大家供大家参考,具体如下: 一、自定义过滤器的介绍 前面我们就介绍过过滤器其实就是一个函数,把要过来的字段传递到一个函数内,进行加...

Python TestCase中的断言方法介绍

Python TestCase中的断言方法介绍

前言 测试是一个贯穿于整个开发过程的连续过程,从某个意义上说,软件开发的过程实际上就是测试过程。正如Martin Fowler所说的"在你不知道如何测试代码之前,就不该编写程序。而一旦你...