杨氏矩阵解法

每日一言

「 人生如逆旅，我亦是行人。 」--临江仙·送钱穆父-苏轼
1

---

题目 杨氏矩阵

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

解法思路

法一：暴力解法

把整个矩阵看成一个二维数组，直接遍历整个数组，寻找数字

代码：

#include
int main()
{
	int arr[][5] = { 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 };
	int i = 0;
	int j = 0;
	int n = 0;
	scanf("%d", &n);
	for (i = 0; i < 5; i++)
	{
		for (j = 0; j < 5; j++)
		{
			if (arr[i][j] == n)
				break;
		}
		if (j < 5)
		{
			printf("有");
			break;
		}
	}
	if(j==5)
	printf("无");
	return 0;
}
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

虽然也能达到效果，但是效率堪忧啊

法二：线性解法

还是这个矩阵，假设我们要找18。
细细品味题目的含义，我们可以这样来找



总结一下刚才的找法

1. 先从右上角查起
2. 判断下面的数与要找的数字的大小关系
3. 如果大于，向左查找。如果小于，继续向下查找
4. 不断循环2,3过程，直到不能再找

按照上述思路，写成代码

#include
int main()
{
	int arr[5][5] = { 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 };
	int i = 0;
	int j = 4;
	int n = 0;
	scanf("%d", &n);
	while (i < 5 && j >= 0)
	{
		if (arr[i][j] == n)
		{
			break;
		}
		else if (arr[i + 1][j] <= n)
		{
			i++;
		}
		else 
		{
			j--;
		}
	}
	if (i < 5 && j >= 0)
		printf("有");
	else
		printf("无");
	return 0;
}
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

---

结语

做这道题时掉进坑里好几次，qwq~

请给自己些耐心，一口吃不成胖子。
山外青山楼外楼，莫把百尺当尽头。
想成为大佬那就保持空杯心态加油努力吧！

---

都看到这里啦！真棒(*^▽^*)

可以给作者一个免费的赞赞吗，这将会鼓励我继续创作，谢谢大家

编程小白写作，如有纰漏或错误，欢迎指正

---