c - 如何在2D阵列中找到鞍点？

我正在尝试编写伪代码来查找2D数组中的所有鞍点。鞍点是这样的点，即值是其行中的最小值，但其列中的最大值，或该行中的最大值和列中的最小值。

我无法确定如何存储这些值的出现位置，特别是在同一行或同一列中有2个鞍点的情况下，我遇到了麻烦。我也不确定我是否正确地解决了这个问题，也许可以用一种更有效的方式来做到这一点？

该数组由A [x] [y]给出，其中x是行，y是列。

到目前为止，我的（非常基本的）伪代码是

for r=0 to y-1    // iterates through every row
    for c=0 to x-1    //iterates through every element in row r
        min=min(A[c][r])   //finds the minimum value in row r
    for p=0 to y-1         //iterates through every element in col c
        max=max(A[c][p])   //finds max in col c
    if min==max
       saddle point=A[c][p]

最佳答案

您的伪代码似乎有两个主要问题。

1）您已经交换了原始数据和列

2）将数组元素（aka值）传递给min / max没有太大意义。您可能应该改为传递行号，并具有返回列号的功能。

一种简单的方法是找到在行r中具有最小值的列的索引。然后找到该列中包含最大值的行的索引。
如果两行索引相同，则您有一个鞍点。

就像是：

for r=0 to x-1    // iterates through every row

    // Check min-max combination

    c = min_in_row(r)       //find index of the column holding the minimum value in row r

    r2 = max_in_column(c)   //find index of the row holding the maximum value in column c

    if (r == r2)
    {
        // Saddle point found
        printf("r=%d c=%d value %d is a saddle point\n", r, c, A[r][c]);
    }

    // Repeat the same for the max-min combination