arrays - 在二维数组中寻找鞍点的算法

Question

我正在寻找一种算法来查找 NxN 矩阵中所有鞍点的位置。

在 StackOverflow 以及其他一般网站上搜索其他答案，我只找到了关于单向运行的鞍点的解决方案。也就是说，我想找到一个鞍点，它可以是行中最大值和列中最小值，或者行中最小值和列中最大值。

例如，给定:

array = {
{ 10, 15, 20, 15, 10 } 
{ 5, 10, 15, 10, 5 }
{ 0, 5, 10, 5, 0 }
{ 5, 10, 15, 10, 5 }
{ 10, 15, 20, 15, 10 } },

鞍点是角落的 10 和中间的 10。

我天真地很容易找到它们，但我想要更高效的东西。有人告诉我它可以在 O(n^2) 中完成。

我想也许我可以固定 x 坐标并遍历 y 坐标以找到所有最大值和最小值，然后通过固定 y 坐标并遍历 x 坐标来反转该过程，但我做不到非常形象化，足以实现这个想法。

如有任何帮助，我们将不胜感激。

Answer 1

请注意，在原始实现 O(n³) 中，您正在重新计算您经过的行/列的每个元素的最大值和最小值。

为了消除这种低效率，我们的想法是遍历每一行和每一列，并在一个单独的 N x N 数组中用最大值和最小值标记所有位置。这个单独数组的每个元素都包含 2 条 bool 信息:isMax 和 isMin(如果需要，可以将其编码为位)。如果一行/列中的所有元素都相同(即最大值 = 最小值)，那么您可能不想标记任何元素。

对于每一行/列，这可以在 O(n) 时间内完成。用一个n元数组记录当前最大(最小)值所在的索引，如果有比当前最大(最小)值更大(更小)的值则清空数组。循环完成后，使用最大(最小)索引数组中的信息标记N x N数组中相应的isMax(isMin)字段。

由于有n行n列，所以这一步的复杂度为O(n²)

然后剩下的就是循环遍历您标记的 N x N 数组，以搜索同时设置了 isMax 和 isMin 的任何位置。