C语言每日一题（3）杨氏矩阵

对编程一片赤诚的小吴

发布于 2024-01-23 14:55:56

1120

发布于 2024-01-23 14:55:56

文章被收录于专栏：热爱编程的证据热爱编程的证据

题目内容

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

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

思路分析

题目中所说的矩阵，大概是这样

1 2 3 4 5

2 3 4 5 6

3 4 5 6 7

4 5 6 7 8

5 6 7 8 9

可以发现，在矩阵里面找数，最基本的方法就是遍历整个数组并判断相等，但这样会发现，矩阵里面有很多重复的数组，如果遍历一遍，效率会低很多，有没有一种高效的方法呢？我们来一起看看，

注意看杨氏矩阵的特点，它的右上角是一行中最大，一列中最小的，且与关联的两条边，会发现它涵盖了矩阵里面所出现的数字，左下角相反，一列中最大，一行中最小的，其实，我们没有必要遍历整个数组，只需要根据我们所定义的起点来遍历外围即可找到所有的数字。

1.以右上角为起点

这里要用一个二维数组来存储整个矩阵，右上角的坐标是arr[0][4]，和它同行比他小，和它同列比他大，如果我们要找的数比他大，就向下遍历，比他小，我就向左遍历，直到找到数字。

int looking_for(int arr[][5], int x, int y, int k)
{
	int i = 0;
	int j = y - 1;
	while (i < x && j >= 0)
	{
		if (arr[i][j] < k)
		{
			i++;
		}
		else if (arr[i][j] > k)
		{
			j--;
		}
		else
		{
			return 1;
		}
	}
	return 0;
}




int main()
{
	int k = 0;
	printf("请输入要寻找的数：");
	scanf("%d", &k);
	int arr[5][5] = { {1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8},{5,6,7,8,9} };
	if (looking_for(arr, 5, 5, k))
	{
		printf("yes\n");
	}
	else
	{
		printf("no\n");
	}
	return 0;
}

2.以左下角为起点

与右上角相反，左下角的下标为arr[4][0],和他同行比他大，和它同列比他小，如果我们要找的数比他大，就向右遍历，比他小，我就向上遍历，直到找到数字。

int looking_for(int arr[][5], int x, int y, int k)
{
	int i = x - 1;
	int j = 0;
	while (j < y && i>=0)
	{
		if (arr[i][j] < k)
		{
			j++;
		}
		else if (arr[i][j] > k)
		{
			i--;
		}
		else
		{
			return 1;
		}
	}
	return 0;
}




int main()
{
	int k = 0;
	printf("请输入要寻找的数：");
	scanf("%d", &k);
	int arr[5][5] = { {1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8},{5,6,7,8,9} };
	if (looking_for(arr, 5, 5, k))
	{
		printf("yes\n");
	}
	else
	{
		printf("no\n");
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-09-14，如有侵权请联系 cloudcommunity@tencent.com 删除

存储