问矩阵中元素邻域的最优检测方法
EN

Stack Overflow用户

提问于 2018-11-06 07:19:18

回答 1查看 61关注 0票数 0

给出了一个维数为n×n的矩阵M。

我必须编写一个算法，返回一对x，y，这样的Mx,y < min(Mx+1,y, Mx,y+1, Mx−1y, Mx,y−1).

当然，你能想到的第一个想法是，取每一个元素，然后逐个检查邻居，看看这种关系是否正确。然而，从时间复杂度的角度来看，该算法必须是最优的。在这里，我不知道如何优化。

有没有人知道我可以搜索的算法的名称，或者给出一些关于如何优化这个算法的提示？

我给了它更多的思考，我认为也许这个算法可以被分解，以求矩阵中的最小值？这肯定能满足上述关系吗？

回答已采纳

发布于 2018-11-06 07:25:39

你在寻找一个当地的最低标准。通过从矩阵中的某个条目开始，并以较小的值进入相邻的条目，很容易找到。

例如，如果您从(x, y)和M[x+1, y] < M[x, y]开始，那么在(x+1, y)继续进行。如果是M[x+1, y-1] < M[x+1, y]，那么在(x+1, y-1)继续。重复直到当前值为局部最小值为止，这意味着您不能再移动到相邻的较小值。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/53167360

复制

相似问题

问矩阵中元素邻域的最优检测方法EN