好资源导航 » 文章资讯 » Python 求数组局部最大值的实例

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

2023-08-07 09:23:06 64

求数组局部最大值

给定一个无重复元素的数组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代码

deflocal_maximum(li):
ifliisNone:
return
left=0
right=len(li)-1
whileleftli[mid+1]:
right=mid
else:
left=mid+1
returnli[left]


if__name__=='__main__':
li=[1,5,2,3,4,0]
result=local_maximum(li)
print(result)

输出结果：4

以上这篇Python求数组局部最大值的实例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

返回顶部
514930285
czq8825@qq.com

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

热门推荐

随机推荐