杨氏矩阵的逆矩阵如何求解？

本文共计991个文字，预计阅读时间需要4分钟。

题目描述：给定一个递增的数字矩阵，每行的元素从左到右递增，每列的元素从上到下递增，请编写程序在该矩阵中查找某个数字是否存在。

要求：

1.使用二维数组实现。

2.限制字数不超过100字。

3.直接输出结果。

代码：

pythondef search_in_matrix(matrix, target): rows=len(matrix) cols=len(matrix[0]) row, col=0, cols - 1 while row =0: if matrix[row][col]==target: return True elif matrix[row][col] > target: col -=1 else: row +=1 return False

示例matrix=[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]target=10result=search_in_matrix(matrix, target)print(result) # 输出：True 或 False

题目描述：

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

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

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

在这样的二维数组中去查找一个数是否存在，我们可以从头遍历一次二维数组，如果可以找到，则元素在矩阵中，否则该矩阵中没有要查找的元素，这种方法下，时间复杂度是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)情况下的解法，如果文章有错误或不妥之处，欢迎评论区留言或私信指出，希望文章对您有帮助，如果觉得文章不错的话请给一个一键三连，我们下期再见！^-^