Python 求數(shù)組局部最大值的實(shí)例
求數(shù)組局部最大值
給定一個(gè)無(wú)重復(fù)元素的數(shù)組A[0…N-1]，求找到一個(gè)該數(shù)組的局部最大值。規(guī)定：在數(shù)組邊界外的值無(wú)窮小。即：A[0]＞A[-1]，A[N-1] ＞A[N]。
顯然，遍歷一遍可以找到全局最大值，而全局最大值顯然是局部最大值。
可否有更快的辦法？
算法描述
使用索引left、right分別指向數(shù)組首尾。
求中點(diǎn) mid = ( left + right ) / 2
A[mid]＞A[mid+1]，丟棄后半段：right=mid
A[mid+1]＞A[mid]，丟棄前半段：left=mid+1
遞歸直至left==right
時(shí)間復(fù)雜度為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)
輸出結(jié)果：4
以上這篇Python 求數(shù)組局部最大值的實(shí)例就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
tensorflow 獲取checkpoint中的變量列表實(shí)例
今天小編就為大家分享一篇tensorflow 獲取checkpoint中的變量列表實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧2020-02-02
解決pytorch load huge dataset(大數(shù)據(jù)加載)
這篇文章主要介紹了解決pytorch load huge dataset(大數(shù)據(jù)加載)的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-05-05
Python數(shù)據(jù)處理篇之Sympy系列(五)---解方程
這篇文章主要介紹了Python數(shù)據(jù)處理篇之Sympy系列(五)---解方程,非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-10-10
Python基礎(chǔ)學(xué)習(xí)之基本數(shù)據(jù)結(jié)構(gòu)詳解【數(shù)字、字符串、列表、元組、集合、字典】
這篇文章主要介紹了Python基礎(chǔ)學(xué)習(xí)之基本數(shù)據(jù)結(jié)構(gòu),結(jié)合實(shí)例形式分析了Python數(shù)字、字符串、列表、元組、集合、字典等基本數(shù)據(jù)類型功能、原理及相關(guān)使用技巧,需要的朋友可以參考下2019-06-06
python3 sorted 如何實(shí)現(xiàn)自定義排序標(biāo)準(zhǔn)
這篇文章主要介紹了python3 sorted 如何實(shí)現(xiàn)自定義排序標(biāo)準(zhǔn)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧2020-03-03
在本篇內(nèi)容里小編給大家整理了一篇關(guān)于python制作抽獎(jiǎng)程序代碼詳解內(nèi)容，需要的朋友們可以參考下。2021-01-01
這篇文章主要介紹了python 解決tqdm模塊不能單行顯示的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧2020-02-02
TensorFlow神經(jīng)網(wǎng)絡(luò)優(yōu)化策略學(xué)習(xí)
這篇文章主要介紹了TensorFlow神經(jīng)網(wǎng)絡(luò)優(yōu)化策略2018-03-03
這篇文章主要介紹了python的迭代器與生成器實(shí)例詳解,需要的朋友可以參考下2014-07-07
一文詳解Python中實(shí)現(xiàn)單例模式的幾種常見方式
這篇文章主要為大家介紹了Python中實(shí)現(xiàn)單例模式的幾種常見方式示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-03-03