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多线程之事件Event的使用详解

前言 小伙伴a,b,c围着吃火锅,当菜上齐了,请客的主人说:开吃!,于是小伙伴一起动筷子,这种场景如何实现 Event(事件) Event(事件):事件处理的机制:全局定义了一个内置标志...

python实现整数的二进制循环移位

python实现整数的二进制循环移位

题目:如何在python中实现整数的二进制循环移位? 概述 在python中,可以通过<<以及>>运算符实现二进制的左移位以及右移位,然而并没有实现循环移位的运算...

基于python3 类的属性、方法、封装、继承实例讲解

Python 类 Python中的类提供了面向对象编程的所有基本功能:类的继承机制允许多个基类,派生类可以覆盖基类中的任何方法,方法中可以调用基类中的同名方法。 对象可以包含任意数量和类...

python 产生token及token验证的方法

1、前言 最近在做微信公众号开发在进行网页授权时,微信需要用户自己在授权url中带上一个类似token的state的参数,以防止跨站攻击。 在经过再三思考之后,自己试着实现一个产生tok...

python反编译学习之字节码详解

前言 如果你曾经写过或者用过 Python,你可能已经习惯了看到 Python 源代码文件;它们的名称以.Py 结尾。你可能还见过另一种类型的文件是 .pyc 结尾的,它们就是 Pyth...