7-1 求解马鞍点问题

2023-10-19 04:04
文章标签 问题 求解 马鞍

本文主要是介绍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 求解马鞍点问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/237177

相关文章

VS配置好Qt环境之后但无法打开ui界面的问题解决

《VS配置好Qt环境之后但无法打开ui界面的问题解决》本文主要介绍了VS配置好Qt环境之后但无法打开ui界面的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 目UKeLvb录找到Qt安装目录中designer.UKeLvBexe的路径找到vs中的解决方案资源

MySQL启动报错:InnoDB表空间丢失问题及解决方法

《MySQL启动报错:InnoDB表空间丢失问题及解决方法》在启动MySQL时,遇到了InnoDB:Tablespace5975wasnotfound,该错误表明MySQL在启动过程中无法找到指定的s... 目录mysql 启动报错:InnoDB 表空间丢失问题及解决方法错误分析解决方案1. 启用 inno

Java使用MethodHandle来替代反射,提高性能问题

《Java使用MethodHandle来替代反射,提高性能问题》:本文主要介绍Java使用MethodHandle来替代反射,提高性能问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录一、认识MethodHandle1、简介2、使用方式3、与反射的区别二、示例1、基本使用2、(重要)

电脑蓝牙连不上怎么办? 5 招教你轻松修复Mac蓝牙连接问题的技巧

《电脑蓝牙连不上怎么办?5招教你轻松修复Mac蓝牙连接问题的技巧》蓝牙连接问题是一些Mac用户经常遇到的常见问题之一,在本文章中,我们将提供一些有用的提示和技巧,帮助您解决可能出现的蓝牙连接问... 蓝牙作为一种流行的无线技术,已经成为我们连接各种设备的重要工具。在 MAC 上,你可以根据自己的需求,轻松地

Java 中的跨域问题解决方法

《Java中的跨域问题解决方法》跨域问题本质上是浏览器的一种安全机制,与Java本身无关,但Java后端开发者需要理解其来源以便正确解决,下面给大家介绍Java中的跨域问题解决方法,感兴趣的朋友一起... 目录1、Java 中跨域问题的来源1.1. 浏览器同源策略(Same-Origin Policy)1.

如何清理MySQL中的binlog问题

《如何清理MySQL中的binlog问题》:本文主要介绍清理MySQL中的binlog问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目http://www.chinasem.cn录清理mysql中的binlog1.查看binlog过期时间2. 修改binlog过期

如何解决yum无法安装epel-release的问题

《如何解决yum无法安装epel-release的问题》:本文主要介绍如何解决yum无法安装epel-release的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录yum无法安装epel-release尝试了第一种方法第二种方法(我就是用这种方法解决的)总结yum

IDEA下"File is read-only"可能原因分析及"找不到或无法加载主类"的问题

《IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题》:本文主要介绍IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题,具有很好的参... 目录1.File is read-only”可能原因2.“找不到或无法加载主类”问题的解决总结1.File

idea中project的显示问题及解决

《idea中project的显示问题及解决》:本文主要介绍idea中project的显示问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录idea中project的显示问题清除配置重China编程新生成配置总结idea中project的显示问题新建空的pr

redis在spring boot中异常退出的问题解决方案

《redis在springboot中异常退出的问题解决方案》:本文主要介绍redis在springboot中异常退出的问题解决方案,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴... 目录问题:解决 问题根源️ 解决方案1. 异步处理 + 提前ACK(关键步骤)2. 调整Redis消费者组