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

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

相关文章

Django+JS 实现点击头像即可更改头像的方法示例

Django+JS 实现点击头像即可更改头像的方法示例

首先,在models.py中创建UserModels类 from django.db import models from django.contrib.auth.models im...

django的auth认证,authenticate和装饰器功能详解

django的auth认证,authenticate和装饰器功能详解

在django中创建表,会自动创建一些django自带的表,先了解用户认证, 认证登录 先要引用 , from django.contrib import auth 有很多方法,...

视觉直观感受若干常用排序算法

视觉直观感受若干常用排序算法

直观感受几种常用排序算法,具体内容如下 1 快速排序 介绍:   快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下...

python 简单搭建阻塞式单进程,多进程,多线程服务的实例

我们可以通过这样子的方式去理解apache的工作原理 1 单进程TCP服务(堵塞式) 这是最原始的服务,也就是说只能处理个客户端的连接,等当前客户端关闭后,才能处理下个客户端,是属于阻塞...

Python中import导入上一级目录模块及循环import问题的解决

import上一级目录的模块 python中,import module会去sys.path搜索,sys.path是个列表,并且我们可以动态修改。 要import某个目录的module,...