本文主要是介绍7-1 求解马鞍点问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
若矩阵Anm中某个元素A[i][j]是矩阵第i行中值最小的元素，同时又是第j列中值最大的元素，则称元素A[i][j]是矩阵中的一个马鞍点。
设以二维数组存储矩阵，编写算法求矩阵A中的所有马鞍点，算法的时间复杂度要尽量的低。
注意当最大值（最小值）并列相等时，会出现多鞍点的情况。
输入格式:
第一行输入矩阵的总行数M和总列数N，以空格间隔。
之后的M行，依次输入矩阵的各行数据，以空格间隔。
输出格式:
若有马鞍点，则以行序为主序，依次输出各个马鞍点。
每个马鞍点以（row,col,val）的形式输出，其中row 代表马鞍点的行号，col代表马鞍点的列号，val代表马鞍点的值。
若无马鞍点，则输出“NONE”。
输入样例:
4 6
45 67 87 34 56 26
93 75 85 75 92 75
94 85 96 75 78 75
23 17 75 28 98 61
输出样例:
(2,4,75)(2,6,75)(3,4,75)(3,6,75)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define M 100
int arr[M][M] = { 0 }, n, m, ans = 0;
vector<int> ind, ind1;
bool check(int x, int y) {for (int i = 1; i <= n; i++) ind1.push_back(i);sort(ind1.begin(), ind1.end(), [&](int i, int j)->bool{return arr[i][y] > arr[j][y];});if (arr[x][y] == arr[ind1[0]][y]) return true;return false;
}
void fun(int x) {for (int i = 1; i <= m; i++) ind.push_back(i);sort(ind.begin(), ind.end(), [&](int i, int j)->bool{return arr[x][i] < arr[x][j];});for (int i = 0; i < m; i++) {if (arr[x][ind[i]] != arr[x][ind[0]]) break;if (!check(x, ind[i])) continue;printf("(%d,%d,%d)",x, ind[i], arr[x][ind[i]]);ans += 1;}return ;
}
int main(){cin >> n >> m;for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> arr[i][j];for (int i = 1; i <= n; i++) {fun(i);ind.clear();ind1.clear();}if (!ans) cout << "NONE" << endl;return 0;
}这篇关于7-1 求解马鞍点问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
