溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

Python 求數(shù)組局部最大值的實(shí)例

發(fā)布時(shí)間：2020-09-16 00:57:13 來源：腳本之家 閱讀：315 作者：RealEmperor 欄目：開發(fā)技術(shù)

求數(shù)組局部最大值

給定一個(gè)無重復(fù)元素的數(shù)組A[0…N-1]，求找到一個(gè)該數(shù)組的局部最大值。規(guī)定：在數(shù)組邊界外的值無窮小。即：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í)例就是小編分享給大家的全部內(nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持億速云。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手