python divide and conquer method to find local peak value of two-dimensional array

Below I will share with you an article on the python divide and conquer method to find the local peak value of a two-dimensional array. It has a good reference value and I hope it will be helpful to everyone. Let’s take a look together

The meaning of the question is roughly to find a local peak in an n*m two-dimensional array. The peak value is required to be greater than the four adjacent elements (outside the array boundary is regarded as negative infinity). For example, if we finally find the peak value A[j][i], then 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]. Returns the coordinates and value of this peak.

Of course, the simplest and most direct method is to traverse all array elements to determine whether they are peak values. The time complexity is O(n^2)

Then optimize a little more to find the value of each row (column) Maximum value, and then find the peak value of the maximum value column through the dichotomy method (the specific method can be found in one-dimensional array to find the peak value). The time complexity of this algorithm is O(logn)

Discussed here It is an algorithm with a complexity of O(n). The algorithm idea is divided into the following steps:

1. Find the word "田". Including the four outer edges and the two horizontal and vertical edges in the middle (the green part in the picture), compare their sizes and find the position of the maximum value. (7 in the picture)

#2. After finding the maximum value in the word Tian, determine whether it is a local peak. If it is, return the coordinate. If not, record the maximum coordinate among the four adjacent points found. Reduce the range through the quadrant where the coordinates are located, and continue to compare the next field character

3. When the range is reduced to 3* 3, the local peak will definitely be found (or it may have been found before)

As to why there must be a peak within the range we choose, you can think of it this way, first we have a circle, we It is known that there is at least one element in a circle that is greater than all the elements in this circle. So, is there a maximum value in this circle?

It may be a bit convoluted, but if you think about it more, you should be able to understand it, and you can also use mathematical proof by contradiction to prove it.

After we understand the algorithm, the next step is to implement the code. The language I use here is python (I am new to python, so please forgive me for some usages that may not be concise enough). Let’s start with the 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()

Copy after login

First of all, my input is written in a txt text file and converted into a two-dimensional array through string conversion. For the specific conversion process, you can read my last blog - Characters in Python Convert string to two-dimensional array. (It should be noted that if the split list does not have an empty tail in the Windows environment, there is no need to add the sentence list.pop()). Some changes are that I added a "0" wall around the two-dimensional array. Adding a wall eliminates the need to consider boundary issues when we judge peak values.

max_sit(*n) function is used to find the position of the maximum value among multiple values and return its position. Python's built-in max function can only return the maximum value, so you still need to write it yourself, *n means Indefinite length parameters, because I need to use this function when comparing fields and ten (judging peak values)

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

Copy after login

dp(s1,s2,e1,e2) The four parameters in the function can be seen as startx, starty, endx, endy. That is, we look for the coordinate values of the upper left corner and lower right corner of the range.

m1 and m2 are the middle values of row and col respectively, which is the middle of the word Tian.

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

Copy after login

Compare the values in 3 rows and 3 columns in order to find the maximum value. Note that the two-dimensional array is required to be a square. If it is a rectangle, adjustments need to be made

 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

Copy after login

Determine whether the maximum value in the word Tian is a peak value, and cannot find the adjacent maximum value

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

Copy after login

Narrow the scope and solve it recursively

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

Copy after login

Okay, the code analysis is basically completed here. If there is anything unclear, please leave a message below.

In addition to this algorithm, I also wrote a greedy algorithm to solve this problem. Unfortunately, the algorithm complexity is still O(n^2) in the worst case, QAQ.

The general idea is to find the largest point among the four adjacent points starting from the middle position, and continue to find the largest adjacent point. Finally, you will definitely find a peak point. If you are interested, you can take a look. , the above code:

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

Copy after login

Related recommendations:

python array search algorithm bisect binary search insertion

Beginner’s python array processing code

Python array filtering implementation method

The above is the detailed content of python divide and conquer method to find local peak value of two-dimensional array_python. For more information, please follow other related articles on the PHP Chinese website!