So erhalten Sie den lokalen Spitzenwert eines zweidimensionalen Arrays in Python-Python-Tutorial-php.cn

Dieses Mal zeige ich Ihnen, wie Sie mit Python den lokalen Spitzenwert eines zweidimensionalen Arrays erhalten. Welche Vorsichtsmaßnahmen gibt es für die Verwendung von Python, um den lokalen Spitzenwert zu erhalten? Das Folgende ist ein praktischer Fall.

Die Bedeutung der Frage besteht grob darin, einen lokalen Peak in einem zweidimensionalen n*m-Array zu finden. Der Spitzenwert muss größer sein als die vier benachbarten Elemente (außerhalb der Array-Grenze wird dies als negative Unendlichkeit angesehen. Wenn wir beispielsweise schließlich den Spitzenwert A[j][i] finden, dann ist A[j][i). ] > A[j+1][i] && A[j][i] > A[j][i] > && A[j][i] > A[j][i-1]. Gibt die Koordinaten und den Wert dieses Peaks zurück.

Der einfachste und direkteste Weg besteht natürlich darin, alle Array-Elemente zu durchlaufen, um festzustellen, ob es sich um Spitzenwerte handelt.

Und dann ein wenig optimieren mehr, um den Maximalwert jeder Zeile (Spalte) zu ermitteln, und ermitteln Sie dann den Spitzenwert der Maximalwertspalte mithilfe der Halbierungsmethode (spezifische Methoden finden Sie unter Eindimensionales Array , um den Spitzenwert zu ermitteln ). Die Zeitkomplexität dieses Algorithmus beträgt O(logn)

Was hier diskutiert wird, ist ein Algorithmus mit einer Komplexität von O(n). Die Algorithmusidee ist in die folgenden Schritte unterteilt :

1. Finden Sie den Charakter „Tian“. Vergleichen Sie unter Einbeziehung der vier Außenkanten und der beiden horizontalen und vertikalen Kanten in der Mitte (der grüne Teil im Bild) deren Größen und ermitteln Sie die Position des Maximalwerts. (7 im Bild)

2. Nachdem Sie den Maximalwert im Wort Tian ermittelt haben, bestimmen Sie, ob dies der Fall ist Wenn dies der Fall ist, geben Sie die Koordinate zurück. Wenn nicht, notieren Sie die maximale Koordinate unter den vier gefundenen benachbarten Punkten. Reduzieren Sie den Bereich durch den Quadranten, in dem sich die Koordinate befindet, und fahren Sie mit dem Vergleichen des nächsten Feldzeichens fort

3 Wann Wenn der Bereich auf 3 * 3 reduziert wird, wird der lokale Peak definitiv gefunden (oder er wurde möglicherweise schon einmal gefunden)

Warum es in dem von uns gewählten Bereich einen Peak geben muss? Sie können es sich so vorstellen: Zuerst haben wir einen Kreis. Es ist bekannt, dass es in einem Kreis mindestens ein Element gibt, das größer ist als alle Elemente in diesem Kreis. Gibt es also einen Maximalwert in diesem Kreis? ?

Es mag etwas kompliziert sein, aber wenn Sie genauer darüber nachdenken, sollten Sie es verstehen können. Sie können es auch mit einem mathematischen Beweis durch Widerspruch beweisen.

Nachdem wir den Algorithmus verstanden haben, besteht der nächste Schritt darin, den Code zu implementieren. Die Sprache, die ich hier verwende, ist Python (ich bin neu in Python, also verzeihen Sie mir bitte einige Verwendungen, die möglicherweise nicht prägnant genug sind). Beginnen wir mit dem Code:

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()

Nach dem Login kopieren

Zuerst wird meine Eingabe in eine TXT-Textdatei geschrieben und über String für den spezifischen Konvertierungsprozess in ein zweidimensionales Array umgewandelt siehe meinen letzten Blog – Konvertieren eines Strings in ein zweidimensionales Python-Dimension-Array. (Es ist zu beachten, dass, wenn die Liste nach der Aufteilung in der Windows-Umgebung kein leeres Ende hat, kein Bedarf besteht, den Satz list.pop() hinzuzufügen.) Einige Änderungen bestehen darin, dass ich eine „0“-Wand um das zweidimensionale Array hinzugefügt habe. Durch das Hinzufügen einer Wand entfällt die Notwendigkeit, Grenzaspekte bei der Beurteilung von Spitzenwerten zu berücksichtigen.

max_sit(*n)-Funktion wird verwendet, um die Position des Maximalwerts unter mehreren Werten zu ermitteln und seine Position zurückzugeben. Die in Python integrierte Max-Funktion kann nur den Maximalwert zurückgeben, daher müssen Sie dies trotzdem tun Schreiben Sie es selbst, *n bedeutet Parameter unbestimmter Länge, da ich diese Funktion verwenden muss, um Tian und Shi zu vergleichen (um den Spitzenwert zu bestimmen)

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

Nach dem Login kopieren

Die vier Parameter in dp(s1,s2, Die Funktion e1,e2 kann als startx, starty, endx, endy angesehen werden. Das heißt, wir suchen nach den Koordinatenwerten der oberen linken Ecke und der unteren rechten Ecke des Bereichs.

m1 und m2 sind die Mittelwerte von row bzw. col, also der Mitte des Wortes Tian.

def dp(s1,s2,e1,e2): 
 m1 = int((e1-s1)/2)+s1   #row 
 m2 = int((e2-s1)/2)+s2   #col

Nach dem Login kopieren

Vergleichen Sie die Werte in 3 Zeilen und 3 Spalten, um den Maximalwert zu ermitteln. Beachten Sie, dass das zweidimensionale Array ein Quadrat sein muss. Anpassungen sind erforderlich gemacht werden

 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

Nach dem Login kopieren

Beurteilen Sie das Wort Tian. Ob der Maximalwert ein Spitzenwert ist und der angrenzende Maximalwert nicht gefunden werden kann

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

Nach dem Login kopieren

Schränen Sie den Bereich ein und lösen Sie ihn rekursiv

 if(sit_row<m1): 
  e1 = m1 
 else: 
  s1 = m1 
 if(sit_col<m2): 
  e2 = m2 
 else: 
  s2 = m2 
 
 return dp(s1,s2,e1,e2)

Nach dem Login kopieren

Okay, die Codeanalyse ist hier im Grunde abgeschlossen. Wenn etwas unklar ist, hinterlassen Sie bitte unten eine Nachricht.

Zusätzlich zu diesem Algorithmus habe ich auch einen Greedy-Algorithmus geschrieben, um dieses Problem zu lösen. Leider ist die Algorithmuskomplexität im schlimmsten Fall immer noch O(n^2), QAQ.

大体的思路就是从中间位置起找相邻4个点中最大的点，继续把该点来找相邻最大点，最后一定会找到一个峰值点，有兴趣的可以看一下，上代码：

#!/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()

Nach dem Login kopieren

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！