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实现确认字符串是否包含指定字符串的实例

有时候我们需要在某段字符串或者某段语句中去查找确认是否包含我们所需要的字符串信息, 举例子说、 某段变量是:A= ”My name is Clay, and you can get my...

python实现高斯判别分析算法的例子

python实现高斯判别分析算法的例子

高斯判别分析算法(Gaussian discriminat analysis) 高斯判别算法是一个典型的生成学习算法(关于生成学习算法可以参考我的另外一篇博客)。在这个算法中,我们假设p...

CentOS7.3编译安装Python3.6.2的方法

CentOS7.3编译安装Python3.6.2的方法

我使用的是 CentOS7.3 安装 Python3.6.2 1.查看是否已经安装Python Centos7 默认安装了Python2.7.5 因为一些命令要用它比如 yum 它使用...

PyTorch中 tensor.detach() 和 tensor.data 的区别详解

PyTorch0.4中,.data 仍保留,但建议使用 .detach(), 区别在于 .data 返回和 x 的相同数据 tensor, 但不会加入到x的计算历史里,且require...

将图片文件嵌入到wxpython代码中的实现方法

将图片文件嵌入到wxpython代码中的实现方法

下面直接上代码留存,方便以后查阅复用。 # -*- coding: utf-8 -*- #作者:LeniyTsan #时间:2014-07-17 import wx from...