Nicn的刷题日常之杨氏矩阵(三种方法求解,逐级递增详解,手把手教学,建议三连收藏)

本文主要是介绍Nicn的刷题日常之杨氏矩阵(三种方法求解,逐级递增详解,手把手教学,建议三连收藏),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.杨氏矩阵知识普及:什么是样式矩阵 

2.题目描述

3.解题 

3.1暴力求解,遍历法

3.2巧妙解题:对角元素法 

3.3将巧解法封装为函数 

4.结语 


1.杨氏矩阵知识普及:什么是样式矩阵 

      杨氏矩阵,是对组合表示理论和舒伯特演算很有用的工具。它提供了一种方便的方式来描述对称和一般线性群的群表示,并研究它们的性质。有一个二维数组. 数组的每行从左到右是递增的,每列从上到下是递增的. 在这样的数组中查找一个数字是否存在。 时间复杂度小于O(N);

而在C语言中,我们通常理解的矩阵就是二维数组,那么 

即是一个杨氏矩阵 。

2.题目描述

有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。

要求:时间复杂度小于O(N);

补充时间复杂度:假设数组有N个元素,遍历这个数组的每个元素去找数字最坏的情况就是将所有元素都遍历一遍,找N次,这时就称时间复杂度为O(n)

时间复杂度描述的是速率,描述最坏的数量积

3.解题 

3.1暴力求解,遍历法

这个办法实现的思想是通过遍历数组的每一个元素来找到某个符合要求的数字,如果1考虑最坏的情况,满足要求的数字刚好是最后一个,那就得把数组从第一个元素到最后一个元素都遍历一遍。这样时间复杂度为O(n),但不失为一种办法,我们来实现一下。

int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int input = 0;printf("请输入您要查找的数字:>");scanf("%d", &input);int i = 0;int j = 0;for (i = 0; i < 3; i++){for (j = 0; j < 3; j++){if (arr[i][j] == input){printf("找到了,下标是%d %d\n", i, j);return;}}}printf("很遗憾没有这个数");return 0;
}

 让我们来看一下运行效果:

那我们刚才也说了,遍历法虽然是可行的但是却达不到我们的时间复杂度要求,所以我们得改进方法,介绍我们的第二种方法对角元素法:

3.2巧妙解题:对角元素法 

对于杨氏矩阵来说,有四个位置的数字是特别的,就是四个对角上的元素:

既然如此我们就可以利用数字3和7这两个位置中的任意一个,例如我们就利用3来查找5:

首先将3和5作比较,由于3是第一行最大元素都小于5,那么第一行的元素就排除,我们行数+1,我们看第二行对应1第一行3的位置的数是6,与5比较大于5,那说明要查找的数5就在第二行当时所在位数的列数小于6所在的列数,所以我们行数确定,列数-1,就找到了5. 

我们来看一下实现过程:

int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int input = 0;printf("请输入您要查找的数字:>");scanf("%d", &input);int i = 0;int j = 2;int flag = 0;while (i<=2&&j>=0){if (arr[i][j] < input){i++;//行数增加,列数不变}else if (arr[i][j] > input){j--;//列数减去1}else{printf("找到了,下标是:%d %d\n", i,j);flag = 1;break;}}if (flag == 0)printf("很抱歉没有找到\n");return 0;
}

 

3.3将巧解法封装为函数 

当封装为一个查找函数的时候,我们就不应该在函数内部进行打印,而是应该在函数外部进行打印,那我们的函数就应该要返回横纵坐标,

这样写可以吗?

return  x,y;

明显这样的返回值是错误的,x,y会被当做为一个逗号表达式进行看待。

所以这里我是直接进行传地址,利用指针传参。我们看一下实现:

void Yang_table_serch(int arr[3][3], int k, int* r, int* c)
{int i = 0;int j = *c - 1;int flag = 0;while (i <= *c-1 && j >= 0){if (arr[i][j] < k){i++;//行数增加,列数不变}else if (arr[i][j] >k){j--;//列数减去1}else{*r = i;*c = j;flag = 1;return;}}if (flag == 0)*r = -1;*c = -1;return;}
int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int input = 0;printf("请输入您要查找的数字:>");scanf("%d", &input);int i = 0;int j = 2;Yang_table_serch(arr, input, &i, &j);if (i == -1 && j == -1){printf("没有找到\n");}else{printf("找到了,下标是:%d %d\n", i, j);}return 0;
}

 

4.结语 

以上就是本期的所有内容,知识含量蛮多,大家可以配合解释和原码运行理解。创作不易,大家如果觉得还可以的话,欢迎大家三连,有问题的地方欢迎大家指正,一起交流学习,一起成长,我是Nicn,正在c++方向前行的奋斗者,感谢大家的关注与喜欢。

      

这篇关于Nicn的刷题日常之杨氏矩阵(三种方法求解,逐级递增详解,手把手教学,建议三连收藏)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据(NaN值)是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值?为什么要统计空值?准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Windows 上如果忘记了 MySQL 密码 重置密码的两种方法

《Windows上如果忘记了MySQL密码重置密码的两种方法》:本文主要介绍Windows上如果忘记了MySQL密码重置密码的两种方法,本文通过两种方法结合实例代码给大家介绍的非常详细,感... 目录方法 1:以跳过权限验证模式启动 mysql 并重置密码方法 2:使用 my.ini 文件的临时配置在 Wi

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.