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实现多线程端口扫描

一个简易的TCP端口扫描器,使用python3实现。 需求:扫描目标网站开放哪些端口号,将所有开放的端口号输出。 分析:使用socket连接,如果连接成功,认为端口开放,如果连接失败,认...

python实现连连看辅助之图像识别延伸

python实现连连看辅助–图像识别延伸(百度AI),供大家参考,具体内容如下 百度AI平台提供图片相似检索API接口,并有详细的API文档说明,可以更好的实现图片识别。 from...

python pandas库中DataFrame对行和列的操作实例讲解

用pandas中的DataFrame时选取行或列: import numpy as np import pandas as pd from pandas import Sereis,...

Python测试人员需要掌握的知识

a、字符串的定义方法 使用单引号(') 你可以用单引号指示字符串,就如同'Quote me on this'这样。所有的空白,即空格和制表符都照原样保留。 使用双引号(") 在双...

Python实现在tkinter中使用matplotlib绘制图形的方法示例

Python实现在tkinter中使用matplotlib绘制图形的方法示例

本文实例讲述了Python实现在tkinter中使用matplotlib绘制图形的方法。分享给大家供大家参考,具体如下: 一. 代码: # coding=utf-8 import s...