查找局部极大值的2D阵列中 [英] Finding local maxima in a 2D array

问题描述

一个局部最大的2D阵列中可被定义为一个值，使得所有这4邻居都小于或等于它，即，对于 A [I] [j]的是本地最大的，

A local maximum in a 2D array can be defined as a value such that all it's 4 neighbours are less than or equal to it, ie, for a[i][j] to be a local maximum,

a[i+1][j] <= a[i][j] 
&& a[i-1][j] <= a[i][j]
&& a[i][j+1] <= a[i][j]
&& a[i+1][j-1] <= a[i][j]

有人问我找一个给定的二维阵列中的所有局部最大值。

I was asked to find all the local maxima in a given 2D array.

天真的方式做，这将是刚刚经过的所有元素，并检查每一个元素是否是本地最大。这将是为O（n ^ 2）。我觉得你不能这样做比这更好的，但我的朋友坚持认为，一个渐近更好的算法应该存在。任何提示？

The naive way to do this would be to just go through all the elements, and checking whether or not each element is a local maximum. This would be O( n^2 ). I feel that you cannot do better than this, although my friend insists that an asymptotically better algorithm should exist. Any hints ?

我一起分而治之的思路思考，但我觉得，这将是不可能检测所有的局部最大值，而无需通过所有的数字，这将必然是为O（n ^ 2）。我说得对还是我错过了一些东西？

I was thinking along the lines of Divide and Conquer, yet I feel that it would be impossible to detect all the local maxima without going through all the numbers, which would necessarily be O( n^2 ). Am I right or am I missing out on something ?

推荐答案

我是pretty的肯定，这不能得到解决，在不到为O（n ^ 2）进行比较。假设一个国际象棋棋盘的二维矩阵，其中所有的白色方块为1和黑人都是0。wiil会有为O（n ^ 2）解决方案，每个解决方案至少需要一个比较。

I am pretty sure this cannot be solved in less than O(n^2) comparisons. Assume a chess board 2d matrix where all the white squares are 1 and blacks are 0. It wiil will have O(n^2) solutions and each solution requires at least one comparison.

这篇关于查找局部极大值的2D阵列中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！