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

相关文章

numpy返回array中元素的index方法

如下所示: import numpy a = numpy.array(([3,2,1],[2,5,7],[4,7,8])) itemindex = numpy.argwhere(a...

Python矩阵常见运算操作实例总结

本文实例讲述了Python矩阵常见运算操作。分享给大家供大家参考,具体如下: python的numpy库提供矩阵运算的功能,因此我们在需要矩阵运算的时候,需要导入numpy的包。 一.n...

在Python中使用M2Crypto模块实现AES加密的教程

 AES(英文:Advanced Encryption Standard,中文:高级加密标准),是一种区块加密标准。AES将原始数据分成多个4×4字节矩阵来处理,通过预先定义的...

Python实现二分法算法实例

1.算法:(设查找的数组期间为array[low, high]) (1)确定该期间的中间位置K (2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域...

python中的全局变量用法分析

本文实例分析了python中的全局变量用法。分享给大家供大家参考。具体分析如下: Python是一种面向对象的开发语言,在函数中使用全局变量,一般应作全局变量说明,只有在函数内经过说明的...