C语言 ——— 在杨氏矩阵中查找具体的某个数
目录
何为杨氏矩阵
题目要求
代码实现
何为杨氏矩阵
可以把杨氏矩阵理解为一个二维数组，这个二维数组中的每一行从左到右是递增的，每一列从上到下是递增的
题目要求
在杨氏矩阵中查找具体的某个数
要求：时间复杂度小于O(N)
代码实现
#include<stdio.h>
int main()
{int arr[3][4] = { {1, 2, 3, 4},{5, 6, 7, 8},{9,10,11,12} };int input = 0;printf("请输入要查找的数：");scanf("%d", &input);// 二维数组的行数int row = sizeof(arr) / sizeof(arr[0]);// 二维数组的列数int col = sizeof(arr[0]) / sizeof(arr[0][0]);// 创建第一行的最后一个元素的下标int x = 0;int y = col - 1;// 查找while (y >= 0 && x < row){// 二维数组的每一行的最后一个元素和input比较if (arr[x][y] < input){// 每次去掉一行x++;}else if (arr[x][y] > input){// 每次去掉一列y--;}else{printf("找到了，下标是：%d %d\n", x, y);break;}}if (y < 0 || x >= row){printf("没找到\n");}return 0;
}代码解析：
二维数组的每一行的最后一个元素，都是当前行里最大的，也是当前列里最小的
所以可以通过 input 直接和每一行的最后一个元素比较，当 input 大于当前行的最大的元素时，声明当前行里肯定没有 input ，当 input 小于当前行的最大的元素时，说明 input 可能在当前行，也有可能找不到，再通过控制列来查找 input
代码验证：
查找到时：
没查找到时：