鞍点的位置

我有以下问题

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

如果矩阵位于某个位置，则称其具有“鞍点” 是其行中的最小值和其列中的最大值。 在符号 中，a[i][j] 是鞍点，如果

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

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

Given 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)，而不是找到最大值/最小值values，你找到他们的indices反而。这可以使第二阶段O(M)在最好的情况下（即当行/列中有唯一的最小值/最大值时）。

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