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杀死一个线程的方法

最近在项目中遇到这一需求: 我需要一个函数工作,比如远程连接一个端口,远程读取文件等,但是我给的时间有限,比如,4秒钟如果你还没有读取完成或者连接成功,我就不等了,很可能对方已经宕机或者...

python常用排序算法的实现代码

这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 排序是计算机语言需要实现的基本算法...

python添加模块搜索路径和包的导入方法

python添加模块搜索路径和包的导入方法

方法一:函数添加 1 import sys 2 查看sys.path 3 添加sys.path.append("c:\\") 方法二:修改环境变量 w用户可以修改系统环境变量PYTHO...

python实现将文本转换成语音的方法

本文实例讲述了python将文本转换成语音的方法。分享给大家供大家参考。具体实现方法如下: # Text To Speech using SAPI (Windows) and Pyt...

Python中的Django基本命令实例详解

一、新建项目 $django-admin.py  startproject  project_name # 特别是在 windows 上,如果报错,尝试用 djang...