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 求数组局部最大值的实例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python+numpy按行求一个二维数组的最大值方法

    问题描述: 给定一个二维数组,求每一行的最大值 返回一个列向量 如: 给定数组[1,2,3:4,5,3] 返回[3:5] import numpy as np x = np.array([[1,2,3],[4,5,3]]) # 先求每行最大值得下标 index_max = np.argmax(x, axis=1)# 其中,axis=1表示按行计算 print(index_max.shape) max = x[range(x.shape[0]), index_max] print(max) # 注

  • 浅谈Python3 numpy.ptp()最大值与最小值的差

    numpy.ptp() 是计算最大值与最小值差的函数,用法如下: import numpy as np a = np.array([np.random.randint(0, 20, 5), np.random.randint(0, 20, 5)]) print('原始数据\n'a) print('对所有数据计算\n', a.ptp()) print('axis=0,按行方向计算,即每列\n', a.ptp(axis=0)) # 按行方向计算,即每列 print('axis=1,按列方向计算,即每

  • python自定义函数实现最大值的输出方法

    python中内置的max()函数用来得到最大值,通过冒泡排序也可以. #!/usr/bin/python def getMax(arr): for i in range(0,len(arr)): for j in range(i+1,len(arr)): first=int(arr[i]) second=int(arr[j]) if first<second: arr[i]=arr[j] arr[j]=first print arr[0] arr1=[19,29,30,48] getMax(a

  • python获取一组数据里最大值max函数用法实例

    本文实例讲述了python获取一组数据里最大值max函数用法.分享给大家供大家参考.具体如下: # 最简单的 max(1, 2) max('a', 'b') # 也可以对列表和元组使用 max([1,2]) max((1,2)) # 还可以指定comparator function max('ah', 'bf', key=lambda x: x[1]) def comparator(x): return x[1] max('ah', 'bf', key=comparator) 希望本文所述对大家

  • Python获取二维矩阵每列最大值的方法

    因为做项目中间有一个很小的环节需要这个功能,所以就写了一个简单的小函数,下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 ''' def get_max_value(martix): ''' 得到矩阵中每一列最大的值 ''' res_list=[] for j in range(len(martix[0])): one_list=[] for i in range(len(martix)): one_list.ap

  • python求最大值最小值方法总结

    python求最大值最小值方法总结

    方法一(常规): 代码: count = int(input('输入数据个数:\n')) a = 1 while a <= count: num = int(input('请输入第{}个数:'.format(a))) #字符串中的方法 if a == 1: #这句一定会执行,而且只执行一次,目的就是让你输入的第一个数作为根据与之后的数比较 max = min = num #第二个及以后的数都会走else, else: #第一次走else时,比较中的min和max都是你第一次输入的数,以后走els

  • Python 实现Numpy中找出array中最大值所对应的行和列

    Python特别灵活,肯定方法不止一种,这里介绍一种我觉得比较简单的方法. 如下图,使用x == np.max(x) 获得一个掩模矩阵,然后使用where方法即可返回最大值对应的行和列. where返回一个长度为2的元组,第一个元素保存的是行号,第二个元素保存的是列号. 以上这篇Python 实现Numpy中找出array中最大值所对应的行和列就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • python求最大值,不使用内置函数的实现方法

    利用python进行求解,求解的要求是不能使用python内部封装好的函数例如:max way1: def findmax(data,n): if n==1: return data[0] else: maxi=data[0] for i in data[1:]: if maxi<i: maxi=i return maxi data=[1,2,34,4] print(findmax(data,len(data))) code result: 34 way2: def getMax(arr): f

  • 实例讲解Python中整数的最大值输出

    在Python中可以存储很大的值,如下面的Python示例程序: x = 10000000000000000000000000000000000000000000; x = x + 1 print (x) 输出: 10000000000000000000000000000000000000000001 在Python中,整数的值不受位数的限制,可以扩展到可用内存的限制.因此,我们永远不需要任何特殊的安排来存储大数字(想象一下在C / C ++中进行上述算术). 在Python 3中,对于所有类型

  • python 判断三个数字中的最大值实例代码

    python 判断三个数字中的最大值,具体代码如下所示: #判断三个数中最大值 n1= int(input('please enter the firest number:')) n2 = int(input('please enter the second number:')) n3 = int(input('please enter the third number:')) max_num = 0 if n1 > n2: max_num = n1 if n1 > n3: max_num =

随机推荐