鞍点的位置

Question

我有以下问题

假设我们有一个9*8矩阵

如果某个位置是某行中的最小值并且其列中的值最大,则称该矩阵具有"鞍点".在符号中,a [i] [j]是一个鞍点

 a[i][j]=min a[i][k]  ==max a[k][k]
             1<=k<=8      1<=k<=9

请帮我找到马鞍点的计算机位置.

Answer 1

给定MxN矩阵，这是O(MN)，这是最优的。

INIT rowMin = [ +Infinify ] xM
INIT colMax = [ -Infinity ] xN

FOR r = 1..M
  FOR c = 1..N
    rowMin[r] = MIN(rowMin[r], mat[r][c])
    colMax[c] = MAX(colMax[c], mat[r][c])

FOR r = 1..M
  FOR c = 1..N
    IF mat[r][c] == rowMin[r] == colMax[c]
       DECLARE saddlePoint(r, c)

为什么这是最佳的？

因为有MxN值，并且每个值都需要查看，所以为了让您的答案是确定的（即不是概率性的），下限是O(MN)。

这个可以进一步优化吗？

你可以稍微优化一下。它仍然会是O(MN)，但不是找到最大/最小值，而是找到它们的索引。这可以使第二阶段O(M)处于最佳情况（即，当行/列中存在唯一的最小值/最大值时）。

请注意，在最坏的情况下，存在O(MN)鞍点：即数组中的数字全部相等时。