一、杨氏矩阵介绍
杨氏矩阵种，每一行的数都从左到右递增，每一列的数都从上到下递增。如下图是一个简单的杨氏矩阵：
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N)
二、查找算法
1.查找思路
杨氏矩阵是很有特点的，它有规律递增的特点决定了针对表中的任一元素，它的下方和右方的数一定大于我，左方和上方的数一定小于我，，所以查找的时候可利用这一特点，从右上角或者左下角来找。
因为这两个位置的大于小于有区分度。例如，若选择从右上角找，那么没有上边和右边，而下边一定比我大，左边一定比我小。那么，如果要查找的数比遍历到的元素大，那我就向下查找；如果比遍历到的元素小，那我就向左查找。
这样查找的次数只有x+y-1次，符合题目中要求的O(n)。
2.步骤
3.代码
int Check(int a[ROW][COL],int row,int col,int k) { int x = 0; int y = col - 1; while(x <= row-1 && y >= 0){ if (k > a[x][y]) { //比我大就向下 x++; } else if (k < a[x][y]) { //比我小就向左 y--; } else { return 1; //相等：找到了 } } return 0; //没有找到 } int main() { int a[ROW][COL] = { {1,2,3,4},{5,6,7,8},{9,10,11,12}};//示例 int k = 0; //要查找的数 printf("请输入你要找的数：\n"); while(~scanf("%d", &k)){ if (Check(a, ROW, COL, k)) { printf("找到了！\n"); } else { printf("该数不存在！\n"); } } return 0; }
三、杨氏矩阵例题
牛客网习题链接
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
代码
该题相当于是前面杨氏矩阵查找的直接运用。注意，当题干中出现 “一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序” 这样的描述时，要立马反应过来它是杨氏矩阵。可能不会每道题的矩阵都像{{1，2，3，4}，{5，6，7，8}，{9，10，11，12}}这样规整，但只要关注并发现它的行按一定顺序（从左到右或从右到左）递增，且列也按一定顺序（从上到下或从下到上）递增，那么就可以运用杨氏矩阵算法。（有时候可能题干数组会是从右向左递增，从下向上递增，刚好和杨氏矩阵反一反，但方法通用。）
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) { int x = 0; int y = *arrayColLen - 1; while(x < arrayRowLen && y >= 0){ if(array[x][y] > target) { y--; }else if(array[x][y] < target) { x++; }else{ return true; } } return false; }
特别注意
针对这串代码，这里必须附上特别说明。传二维数组入函数，函数头写了形参为int** array，注意这并不是直接传二维数组名时的形参接收方式。
若实参部分直接传二维数组数组名array，则形参应写为：
//列参数不可省略 void fun(int array[][col]);
或
//一维数组指针 void fun(int (*array)[col]);
而用int** array接收，则调用方应该这样写：
#include<stdio.h> bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) { int x = 0; int y = *arrayColLen - 1; while(x < arrayRowLen && y >= 0){ if(array[x][y] > target) { y--; }else if(array[x][y] < target) { x++; }else{ return true; } } return false; } int main(){ int a1[]={1,2,8,9}; int a2[]={2,4,9,12}; int a3[]={4,7,10,13}; int a4[]={6,8,11,15}; int* p[] = {a1,a2,a3,a4}; int arrayRowLen = 4; int arrayColLen = 4; //传入指针数组的数组名，数组p内的元素是指针类型，存放的是另外四个一维数组名 printf("%d",Find(100, p,arrayRowLen ,&arrayColLen)); return 0; }
四、总结
概括来说，杨氏矩阵查找的算法是根据杨氏矩阵中数递增规律特点设计的，而这种设计算法的思路可以迁移。若题干变换为其它类型的、其中数具有变化规律的矩阵，要能想起杨氏矩阵的查找算法，并尝试将这种设计的思路迁移到变式中去。
