杨氏矩阵

题目描述：

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

根据题目要求我们可以利用二维数组实现一个杨氏矩阵。

如下图所示，我们可以看到矩阵每行从左到右递增，从上到下递增。

在这样的二维数组中去查找一个数是否存在，我们可以从头遍历一次二维数组，如果可以找到，则元素在矩阵中，否则该矩阵中没有要查找的元素，这种方法下，时间复杂度是O(N)。

但是如果题目更改要求，要求时间复杂度小于O(N)，那么我们该怎么做呢？

分析杨氏矩阵，我们发现矩阵中存在着一些特殊位置的元素，比如说矩阵右上角的元素，这个元素是其所处行的最大元素，是其所处列的最小元素。那么在输入查找元素key后，我们可以以该元素为比较出发点：

如果key<3:

那么由于3是最后一列上最小的元素，而key比3还要小，所以key肯定不会在最后一列上，这样我们就可以直接排除最后一列，列指向第二列，继续向前查找。

如果key>3:

那么由于3是第一行上最大的元素，而key比3还要大，所以key肯定不会在第一行上，这样我们就可以直接排除第一行，行指向第二行，继续向下查找。

如果key==3:

那么矩阵中存在元素key，可以直接返回。

.....

就这样每次都从矩阵右上角的元素开始查找，一次排除一行或者一列，则可以实现时间复杂度小于O(N)。

查找最后有两种结果：

• 找到key值，返回。
• 行值自增超过矩阵行数2/列值自减<0，查找结束。

最后附上代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//杨氏矩阵
int main()
{
	int arr[3][3] = { {1,2,3},{3,4,5},{5,6,7} };
	int k = 0;
	scanf("%d", &k);
	int row = 3;
	int col = 3;
	int i = 0;
	int j = col-1;
	while(i<row)
	{
		while(j>=0)
		{
			if (k < arr[i][j])
			{
				j--;
			}
			else if (k > arr[i][j])
			{
				i++;
			}
			else
			{
				printf("找到了，下标为%d,%d", i, j);
				return 0;
			}
		}
		if (j < 0)break;
	}
	printf("%d不在该矩阵中\n",k);

	return 0;
}

以上就是杨氏矩阵查找在时间复杂度小于O(N)情况下的解法，如果文章有错误或不妥之处，欢迎评论区留言或私信指出，希望文章对您有帮助，如果觉得文章不错的话请给一个一键三连，我们下期再见！^-^