登录  /  注册

python如何取得二维数组局部峰值

php中世界最好的语言
发布: 2018-05-25 11:26:46
原创
4219人浏览过

这次给大家带来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,可能有些用法上不够简洁请见谅),先上代码:

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 f list for row_n col_n ans_sit print f.close><p style="text-align: left;">首先我的输入写在txt文本文件里,通过<a href="http://www.php.cn/wiki/57.html" target="_blank">字符串</a>转换变为二维数组,具体转换过程可以看我上一篇博客——<strong>python中字符串转换为二维数组</strong>。(需要注意的是如果在<a href="http://www.php.cn/php/php-Windows-environment.html" target="_blank">windows环境</a>中split后的列表没有空尾巴,所以不用加list.pop()这句话)。有的变动是我在二维数组四周加了“0”的围墙。加围墙可以再我们判断峰值的时候不用考虑边界问题。</p>
<p style="text-align: left;">max_sit(*n)函数用于找到多个值中最大值的位置,返回其位置,python的内构的max函数只能返回最大值,所以还是需要自己写,*n表示不定长参数,因为我需要在比较田和十(判断峰值)都用到这个函数</p>
<pre class="brush:php;toolbar:false">def max_sit(*n):     #返回最大元素的位置
 temp = 0
 sit = 0
 for i in range(len(n)):
  if(n[i]&gt;temp):
   temp = n[i]
   sit = i
 return sit
登录后复制

dp(s1,s2,e1,e2)函数中四个参数的分别可看为startx,starty,endx,endy。即我们查找范围左上角和右下角的坐标值。

m1,m2分别是row 和col的中间值,也就是田字的中间。

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

依次比较3行3列中的值找到最大值,注意这里要求二维数组为正方形,如果为矩形需要做调整

 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
登录后复制

判断田字中最大值是不是峰值,并找不出相邻最大值

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><p style="text-align: left;">好了,到这里代码基本分析完了。如果还有不清楚的地方欢迎下方留言。</p>
<p style="text-align: left;">除了这种算法外,我也写一种贪心算法来求解这道题,只可惜最坏的情况下算法复杂度还是O(n^2),QAQ。</p>
<p style="text-align: left;">大体的思路就是从中间位置起找相邻4个点中最大的点,继续把该点来找相邻最大点,最后一定会找到一个峰值点,有兴趣的可以看一下,上代码:</p>
<pre class="brush:php;toolbar:false">#!/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()
登录后复制

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

推荐阅读:

Python接口使用OpenCV的方法

Python变量赋值的步奏详解

以上就是python如何取得二维数组局部峰值的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号