algorithm - 鞍点的位置

Question

我有以下问题

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

一个矩阵被称为有一个“鞍点”，如果在某个位置是其行中的最小值和其列中的最大值。在 symbols 中，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) 个鞍点:即数组中的数字都相等。