题目概要
有一个数字矩阵,矩阵的每行从左到右都是递增的,矩阵从上到下都是递增的,请编写程序在这样的矩阵中查找某个数字是否存在?
一、解题思路
对于查找一个数组中元素是否存在,很多同学第一想法就是从头到尾遍历一遍。这样的想法优点是代码简单且无脑容易上手,但是这样的缺点也很明显,比如是m *n的数组,你从头到尾遍历,最坏情况要找m *n次。题目给的相关条件比如从左向右递增,从上向下递增你也完全没有使用,这样的暴力求解显然不是我们想看到的
我们来介绍一种方法,以下列二维数组进行举例
1 2 3
4 5 6
7 8 9
根据矩阵的每行从左到右都是递增这个特性,我们知道矩阵的每一行最后一个数都是该行最大的,比如上面这个矩阵的3,6,9。对于7是否在这个矩阵中,我们可以与每行的最后一个数比较,如果7小于当前行,则在当前行遍历,否则进行与下一行最后一个数的比较,如果最后一行都小于7说明7是不在该矩阵中的
二、具体代码
代码如下(示例):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<stdio.h>
void find( int arr[3][3], int k, int h, int l) //h和l分别表示行和列
{
int x = 0; //第一行横坐标
int y = l - 1; //第一行最后一列纵坐标
for (x = 0,y = l - 1;arr[x][y] < k&&x<=h-1;x++) //判断条件多加一个x<h-1是防止越数组访问
{
; //过滤掉无用的行
}
if (x == h) //x==h说明所有行都不匹配
{
printf ( "该数组没有这个数\n" );
}
else if (arr[x][y]>k)
{
int i = 0;
for (i = 0;i < l;i++)
{
if (k == arr[x][i])
{
printf ( "找到了,该数在第%d行,第%d列" , x+1, i + 1);
}
}
}
else if (arr[x][y] == k)
{
printf ( "找到了,该数在第%d行,第%d列" , x + 1, y + 1);
}
}
int main()
{
int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
int k = 0;
printf ( "请问你要查找的数是:" );
scanf ( "%d" , &k);
find(arr, k, 3, 3);
}
|
以上就是C语言编程题杨氏矩阵算法快速上手示例详解的详细内容,更多关于C语言编程杨氏矩阵算法的资料请关注服务器之家其它相关文章!
原文链接:https://blog.csdn.net/m0_57180439/article/details/120252334