以下就為大家分享一篇python分治法求二維數組局部峰值方法,具有很好的參考價值,希望對大家有幫助。一起來看看吧
題目的意思大致是在一個n*m的二維數組中,找到一個局部峰值。峰值要求大於相鄰的四個元素(數組邊界以外視為負無窮),例如最後我們找到峰值A[j][i],則有A[j][i] > A[j+1][ i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1]。傳回該峰值的座標和值。
當然,最簡單直接的方法就是遍歷所有數組元素,判斷是否為峰值,時間複雜度為O(n^2)
再優化一點求每一行(列)的最大值,再透過二分法找最大值列的峰值(具體方法可見一維數組求峰值),這種演算法時間複雜度為O(logn)
這裡討論的是複雜度為O(n)的演算法,演算法思路分為以下幾個步驟:
1、找「田」字。包括外圍的四邊和中間橫豎兩條邊(圖中綠色部分),比較其大小,找出最大值的位置。 (圖中的7)

#2、找到田字中最大值後,判斷它是不是局部峰值,如果是傳回該座標,如果不是,記錄找到相鄰四個點中最大值座標。透過此座標所在的象限縮小範圍,繼續比較下一個田字

3、當範圍縮小到3* 3時必定會找到局部峰值(也可能之前就找到了)
關於為什麼我們選擇的範圍內一定存在峰值,大家可以這樣想,首先我們有一個圈,我們已知有圈內至少有一個元素大於這個圈所有的元素,那麼,是不是這個圈中一定有一個最大值?
可能說得有點繞,但多想想應該可以理解,也可以用數學的反證法來證明。
演算法我們理解後接下來就是程式碼實現了,這裡我用的語言是python(初學python,可能有些用法上不夠簡潔請見諒),先上程式碼:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | import numpy as np
def max_sit(*n): #返回最大元素的位置
temp = 0
sit = 0
for i in range(len(n)):
if (n[i]>temp):
temp = n[i]
sit = i
return sit
def dp(s1,s2,e1,e2):
m1 = int((e1-s1)/2)+s1 #row
m2 = int((e2-s1)/2)+s2 #col
nub = e1-s1
temp = 0
sit_row = 0
sit_col = 0
for i in range(nub):
t = max_sit(list[s1][s2+i], #第一排
list[m1][s2+i], #中间排
list[e1][s2+i], #最后排
list[s1+i][s2], #第一列
list[s1+i][m2], #中间列
list[s1+i][e2], #最后列
temp)
if (t==6):
pass
elif(t==0):
temp = list[s1][s2+i]
sit_row = s1
sit_col = s2+i
elif(t==1):
temp = list[m1][s2+i]
sit_row = m1
sit_col = s2+i
elif(t==2):
temp = list[e1][s2+i]
sit_row = e1
sit_col = s2+i
elif(t==3):
temp = list[s1+i][s2]
sit_row = s1+i
sit_row = s2
elif(t==4):
temp = list[s1+i][m2]
sit_row = s1+i
sit_col = m2
elif(t==5):
temp = list[s1+i][e2]
sit_row = s1+i
sit_col = m2
t = max_sit(list[sit_row][sit_col], #中
list[sit_row-1][sit_col], #上
list[sit_row+1][sit_col], #下
list[sit_row][sit_col-1], #左
list[sit_row][sit_col+1]) #右
if (t==0):
return [sit_row-1,sit_col-1]
elif(t==1):
sit_row-=1
elif(t==2):
sit_row+=1
elif(t==3):
sit_col-=1
elif(t==4):
sit_col+=1
if (sit_row<m1):
e1 = m1
else :
s1 = m1
if (sit_col<m2):
e2 = m2
else :
s2 = m2
return dp(s1,s2,e1,e2)
f = open("demo.txt","r")
list = f.read()
list = list.split("\n") #对行进行切片
list = ["0 "*len(list)]+list+["0 "*len(list)] #加上下的围墙
for i in range(len(list)): #对列进行切片
list[i] = list[i].split()
list[i] = ["0"]+list[i]+["0"] #加左右的围墙
list = np. array (list).astype(np.int32)
row_n = len(list)
col_n = len(list[0])
ans_sit = dp(0,0,row_n-1,col_n-1)
print ("找到峰值点位于:",ans_sit)
print ("该峰值点大小为:",list[ans_sit[0]+1,ans_sit[1]+1])
f.close()
|
登入後複製
首先我的輸入寫在txt文字檔案裡,透過字串轉換變成二維數組,具體轉換過程可以看我上一篇部落格-python中字符串轉換為二維數組。 (要注意的是如果在windows環境中split後的列表沒有空尾巴,所以不用加list.pop()這句話)。有的變動是我在二維數組四周加了“0”的圍牆。加圍牆可以再我們判斷峰值的時候不用考慮邊界問題。
max_sit(*n)函數用來找出多個值中最大值的位置,傳回其位置,python的內構的max函數只能傳回最大值,所以還是需要自己寫,*n表示不定長參數,因為我需要在比較田和十(判斷峰值)都用到這個函數
1 2 3 4 5 6 7 8 | def max_sit(*n): #返回最大元素的位置
temp = 0
sit = 0
for i in range(len(n)):
if (n[i]>temp):
temp = n[i]
sit = i
return sit
|
登入後複製
dp(s1,s2,e1,e2)函數中四個參數的分別可看為startx,starty,endx,endy。即我們查找範圍左上角和右下角的座標值。
m1,m2分別是row 和col的中間值,也就是田字的中間。
1 2 3 | def dp(s1,s2,e1,e2):
m1 = int((e1-s1)/2)+s1 #row
m2 = int((e2-s1)/2)+s2 #col
|
登入後複製
依序比較3行3列中的值找到最大值,注意這裡要求二維陣列為正方形,如果為矩形需要做調整
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | for i in range(nub):
t = max_sit(list[s1][s2+i], #第一排
list[m1][s2+i], #中间排
list[e1][s2+i], #最后排
list[s1+i][s2], #第一列
list[s1+i][m2], #中间列
list[s1+i][e2], #最后列
temp)
if (t==6):
pass
elif(t==0):
temp = list[s1][s2+i]
sit_row = s1
sit_col = s2+i
elif(t==1):
temp = list[m1][s2+i]
sit_row = m1
sit_col = s2+i
elif(t==2):
temp = list[e1][s2+i]
sit_row = e1
sit_col = s2+i
elif(t==3):
temp = list[s1+i][s2]
sit_row = s1+i
sit_row = s2
elif(t==4):
temp = list[s1+i][m2]
sit_row = s1+i
sit_row = m2
elif(t==5):
temp = list[s1+i][e2]
sit_row = s1+i
sit_row = m2
|
登入後複製
判斷田字中最大值是不是峰值,並找不到相鄰最大值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | t = max_sit(list[sit_row][sit_col], #中
list[sit_row-1][sit_col], #上
list[sit_row+1][sit_col], #下
list[sit_row][sit_col-1], #左
list[sit_row][sit_col+1]) #右
if (t==0):
return [sit_row-1,sit_col-1]
elif(t==1):
sit_row-=1
elif(t==2):
sit_row+=1
elif(t==3):
sit_col-=1
elif(t==4):
sit_col+=1
|
登入後複製
縮小範圍,遞迴求解
1 2 3 4 5 6 7 8 9 10 | if (sit_row<m1):
e1 = m1
else :
s1 = m1
if (sit_col<m2):
e2 = m2
else :
s2 = m2
return dp(s1,s2,e1,e2)
|
登入後複製
好了,到這裡程式碼基本分析完了。如果還有不清楚的地方歡迎下方留言。
除了這個演算法外,我也寫一種貪心演算法來解這題,只可惜最壞的情況下演算法複雜度還是O(n^2),QAQ。
大體的想法就是從中間位置起找相鄰4個點中最大的點,繼續把該點來找相鄰最大點,最後一定會找到一個峰值點,有興趣的可以看一下,上碼:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #!/usr/bin/python3
def dp(n):
temp = (str[n],str[n-9],str[n-1],str[n+1],str[n+9]) #中 上 左 右 下
sit = temp.index(max(temp))
if (sit==0):
return str[n]
elif(sit==1):
return dp(n-9)
elif(sit==2):
return dp(n-1)
elif(sit==3):
return dp(n+1)
else :
return dp(n+9)
f = open("/home/nancy/桌面/demo.txt","r")
list = f.read()
list = list.replace(" ","").split() #转换为列表
row = len(list)
col = len(list[0])
str="0"*(col+3)
for x in list: #加围墙 二维变一维
str+=x+"00"
str+="0"*(col+1)
mid = int(len(str)/2)
print (str,mid)
p = dp(mid)
print (p)
f.close()
|
登入後複製
相關推薦:
python數組查找演算法bisect二分查找插入
#初學python陣列的處理代碼
python陣列過濾實作方法
#################################################### ##
以上是python分治法求二維數組局部峰值方法_python的詳細內容。更多資訊請關注PHP中文網其他相關文章!