首頁 後端開發 Python教學 python分治法求二維數組局部峰值方法_python

python分治法求二維數組局部峰值方法_python

Apr 08, 2018 am 11:40 AM
python 局部 陣列

以下就為大家分享一篇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中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱門文章

兩個點博物館:邦格荒地地點指南
4 週前 By 尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章

兩個點博物館:邦格荒地地點指南
4 週前 By 尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱門文章標籤

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

怎麼下載deepseek 小米 怎麼下載deepseek 小米 Feb 19, 2025 pm 05:27 PM

怎麼下載deepseek 小米

模板化的優點和缺點有哪些? 模板化的優點和缺點有哪些? May 08, 2024 pm 03:51 PM

模板化的優點和缺點有哪些?

Google AI 為開發者發佈 Gemini 1.5 Pro 和 Gemma 2 Google AI 為開發者發佈 Gemini 1.5 Pro 和 Gemma 2 Jul 01, 2024 am 07:22 AM

Google AI 為開發者發佈 Gemini 1.5 Pro 和 Gemma 2

deepseek怎麼問他 deepseek怎麼問他 Feb 19, 2025 pm 04:42 PM

deepseek怎麼問他

NET40是什麼軟體 NET40是什麼軟體 May 10, 2024 am 01:12 AM

NET40是什麼軟體

deepseek該怎麼搜索 deepseek該怎麼搜索 Feb 19, 2025 pm 05:18 PM

deepseek該怎麼搜索

瀏覽器插件是什麼語言寫的 瀏覽器插件是什麼語言寫的 May 08, 2024 pm 09:36 PM

瀏覽器插件是什麼語言寫的

deepseek怎麼編程 deepseek怎麼編程 Feb 19, 2025 pm 05:36 PM

deepseek怎麼編程

See all articles