查找线性时间的算法来查找元件，它是最小的其在2D阵列neigbours的

-4

鉴于N * N的阵列，得到O（n）的算法以找出对指数i的和j使得A[i][j] < A[i-1][j]，A[i][j] < A[i+1][j]，A[i][j] < A[i][j-1]和A[i][j] < A[i][j+1]。查找线性时间的算法来查找元件，它是最小的其在2D阵列neigbours的

2012-03-25 user_pvr

这是不可能的，除非有更多的限制我们没有被告知。您调查的每个职位最多可排除/验证5个职位，因此通过查看k职位（及其邻居），您最多可排除/验证5*k职位。

2012-03-25 14:06:08

不，这不是不可能的。有一个分而治之的算法。 – han 2012-03-25 16:31:29

我很好奇。这将如何工作？ – 2012-03-25 16:49:03

@han如果有一个分而治之的算法来解决这个问题，而不是看所有的元素，我真的很想看到它。在那之前，我很确定没有这样的算法存在，并且按照规定解决问题实际上是不可能的。 – sepp2k 2012-03-26 10:04:15

回答