C++ 寻找马鞍数 - 算法实现与代码解析

本文介绍了马鞍数的概念，并提供 C++ 代码实现，用于查找矩阵中的马鞍数。代码示例清晰易懂，附带详细注释，帮助理解算法逻辑。

马鞍数定义

在矩阵中，如果一个元素是其所在行中的最小值，同时也是其所在列中的最大值，那么这个元素就被称为马鞍数。

算法思路

1. 遍历矩阵，对于每个元素，判断它是否为所在行的最小值。 2. 如果是，则进一步判断它是否为所在列的最大值。 3. 如果是，则将其加入马鞍数列表。

代码实现

#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector&lt;vector&lt;int&gt;&gt; matrix(n, vector&lt;int&gt;(m));
for (int i = 0; i &lt; n; i++) {
    for (int j = 0; j &lt; m; j++) {
        cin &gt;&gt; matrix[i][j];
    }
}

vector&lt;pair&lt;int, pair&lt;int, int&gt;&gt;&gt; saddlePoints;
for (int i = 0; i &lt; n; i++) {
    int minRow = matrix[i][0];
    int minColIndex = 0;
    for (int j = 1; j &lt; m; j++) {
        if (matrix[i][j] &lt; minRow) {
            minRow = matrix[i][j];
            minColIndex = j;
        }
    }
    
    bool isSaddlePoint = true;
    for (int k = 0; k &lt; n; k++) {
        if (matrix[k][minColIndex] &gt; minRow) {
            isSaddlePoint = false;
            break;
        }
    }
    
    if (isSaddlePoint) {
        saddlePoints.push_back({minRow, {i, minColIndex}});
    }
}

if (saddlePoints.empty()) {
    cout &lt;&lt; "not exist" &lt;&lt; endl;
} else {
    for (const auto& saddlePoint : saddlePoints) {
        cout &lt;&lt; saddlePoint.second.first + 1 &lt;&lt; " " &lt;&lt; saddlePoint.second.second + 1 &lt;&lt; " " &lt;&lt; saddlePoint.first &lt;&lt; endl;
    }
}

return 0;

}

代码解析

1. 定义矩阵：使用 vector<vector<int>> 表示矩阵，并读取输入数据。

2. 遍历矩阵：使用双重循环遍历矩阵中的每个元素。

3. 寻找行最小值：在每一行中找到最小值，以及最小值所在的列索引。

4. 寻找列最大值：判断行最小值是否为所在列的最大值。如果所有列中的元素都小于等于行最小值，则该元素为马鞍数。

5. 输出结果：如果存在马鞍数，则输出所有马鞍数的行号、列号以及马鞍数本身。如果不存在马鞍数，则输出 "not exist"。

总结

本文介绍了马鞍数的概念，并通过 C++ 代码实现算法，帮助理解和实现马鞍数的查找。代码示例清晰易懂，注释详细，方便理解和学习。