亲宝软件园·资讯

展开

C语言杨氏矩阵简单实现方法

折木` 人气:0

今天来向大家介绍一个用C语言实现杨氏矩阵的问题。题目如下:

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

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

题干中所描述的矩阵被称作杨氏矩阵,然后让你在这个这个矩阵中查找一个数字。其实在矩阵中查找一个数字并不难,只需采取遍历的方式,将矩阵中每个元素拿出来比较即可。但这道题还有一个要求就是时间复杂度必须小于O(N),也就是说不能采用遍历的方式来查找。因此我们需要根据杨氏矩阵的特点来写一个新的算法进行查找。

如下图所示,为一个3x3的杨氏矩阵。

根据题目我们总结一下杨氏矩阵的两个特点:

1. 同一行的元素由左向右依次递增

2. 同一列的元素从上到下依次递增

通过这两点我们会发现这个矩阵有两个元素是特殊元素。

因此我们可以采用以下方法:

先拿出右上角的元素3来和所查找的元素比较,如果3比要查找的元素大,那说明该元素绝不可能在第一行,因此我们就可以直接排除一行的元素。如果3比要查找的元素小,那说明该元素绝不可能在最后一列,因此我们就可以直接排除一列的元素

现在假设我们排除了一行的元素,那接下来的矩阵就变成了这样:

这时6又变成了右上角的元素,然后重复上一步的操作,假设我们这次排除了一列的元素,那接下来的矩阵就变成了这样:

于是5变成了右上角的元素,继续重复上一步操作,这样每一次查找我们都可以排除一行或者一列的元素,大大的提高了算法效率。

当然上述举例我是以右上角元素为基准的,如果以左下角元素为基准也可以得到相同的结果,大家不妨自己来试一下。

实现代码如下:

#include <stdio.h>
int find_num(int arr[3][3], int row, int col, int k)
{
	int x = 0;
	int y = col-1;
	while (x<row && y>=0)
	{
		if (arr[x][y] == k)
		{
			printf("下标为: %d %d\n", x, y);
			return 1;
		}
		else if (arr[x][y] > k)
			y--;
		else if (arr[x][y] < k)
			x++;
	}
	return 0;
}
int main()
{
	int arr[3][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int ret = find_num(arr, 3, 3, 7);
	if (ret == 1)
		printf("找到了\n");
	else
		printf("找不到\n");
	return 0;
}

这里我们将查找杨氏矩阵元素的过程封装在一个函数中。函数接收4个参数,分别是二维数组的地址,行数,列数和要查找的元素。通过返回值来判断是否找到。

在函数内部定义一个坐标(x, y)表示右上角元素,当x等于行数是说明已经越界(数组下标是从0开始的),那要查找的元素必然不存在。当列数小于0也一样。

当排除一行的时候,给x的值加1即可;排除一列的时候,给y的值减1即可。

运行结果:

加载全部内容

相关教程
猜你喜欢
用户评论