杨氏矩阵查找一、问题描述在一个矩阵中查找某个数字是否存在该矩阵满足每行从左到右递增每列从上到下递增像这样1 3 5 7 2 4 6 8 3 5 7 9 4 6 8 10这种矩阵称为杨氏矩阵Young Tableau任务是在其中快速定位目标值。二、核心解法从右上角开始算法步骤从矩阵的右上角开始target 当前值→ ✅ 找到了target 当前值→ 向左移动排除当前列target 当前值→ 向下移动排除当前行重复直到找到或越界动画模拟以查找target 6为例起点 → 右上角 7 6 7 → 左移排除第4列 ↓ 1 3 5 [7] ← 第1步76左移 2 4 6 8 3 5 7 9 4 6 8 10 1 3 [5] 7 ← 第2步56下移 2 4 6 8 3 5 7 9 4 6 8 10 1 3 5 7 2 4 [6] 8 ← 第3步66找到✅ 3 5 7 9 4 6 8 10 位置[1][2]为什么从右上角右上角元素具有唯一的方向判断往左 → 元素变小 往下 → 元素变大 target 当前值 → 只能往下走排除当前行 target 当前值 → 只能往左走排除当前列每次比较都能确定地排除一整行或一整列不犹豫三、为什么不能从左上角从左上角开始的话往右 → 元素变大 往下 → 元素变大 target 当前值 → 往右还是往下 两个方向都有可能 无法确定唯一路径结论左上角和右下角都不可用因为两个方向同大同小路径不唯一。四、四个起始位置对比起始位置是否可用原因右上角✅ 可用左边小下边大方向唯一左下角✅ 可用上边小右边大方向唯一左上角❌ 不行右边和下边都大方向不唯一右下角❌ 不行左边和上边都小方向不唯一记忆技巧选对角的两个位置右上 / 左下一边大一边小方向才唯一。五、完整代码实现#includestdio.h#defineROWS4#defineCOLS4/** * 杨氏矩阵查找 * param matrix 矩阵 * param rows 行数 * param cols 列数 * param target 目标值 * param row 输出参数找到的行号 * param col 输出参数找到的列号 * return 1找到, 0未找到 */intfind_in_matrix(intmatrix[][COLS],introws,intcols,inttarget,int*row,int*col){inti0;// 从第 0 行开始intjcols-1;// 从最后一列开始右上角while(irowsj0){if(matrix[i][j]target){*rowi;// 记录找到的位置*colj;return1;// 找到}elseif(matrix[i][j]target){j--;// 当前值太大 → 向左移动排除当前列}else{i;// 当前值太小 → 向下移动排除当前行}}return0;// 越界未找到}intmain(){intmatrix[ROWS][COLS]{{1,3,5,7},{2,4,6,8},{3,5,7,9},{4,6,8,10}};inttarget6;introw,col;if(find_in_matrix(matrix,ROWS,COLS,target,row,col)){printf(找到了位置 [%d][%d]\n,row,col);// 输出找到了位置 [1][2]}else{printf(未找到\n);}return0;}复杂度分析维度值说明时间复杂度O(m n)每次移动排除一行或一列最多 mn 步空间复杂度O(1)只用了 i、j 两个变量比暴力遍历的 O(m×n) 快得多六、指针参数详解⚠️ 重要为什么用int* row, int* colintfind_in_matrix(...,int*row,int*col)row和col是指针参数存储main()中变量的地址通过*row i和*col j可以直接修改main()中的变量函数返回值已被用来表示是否找到位置信息通过指针传出函数结束后修改的值会被释放吗答案不会✅内存图解main() 中: int row, col; // row 在地址 0x100col 在地址 0x104 调用函数: find_in_matrix(..., row, col); // 传入的是 row 和 col 的地址 函数内部: int* row 0x100; // 指针本身存在栈上地址 0x200 int* col 0x104; // 指针本身存在栈上地址 0x204 *row i; // 往 0x100 写入 → 修改 main 中的 row ✅ *col j; // 往 0x104 写入 → 修改 main 中的 col ✅ 函数结束: ❌ 指针变量 row、col 本身被释放0x200、0x204 ✅ 但 0x100、0x104 中的值已被修改保留在 main() 中生动类比你把家里钥匙 ️指针交给朋友函数 朋友开门放了东西*row i 朋友走了函数结束钥匙销毁指针释放 但你家里的东西还在main 中的变量已被修改什么时候会失效只有一种情况把局部变量的地址传出去。voidbad(int**p){intlocal10;*plocal;// ❌ 局部变量地址传出}// local 被释放 → 外部拿到野指针功能失效// 本题中安全的原因// row 和 col 指向的是 main() 中的变量// 这些变量在 main() 结束前都一直存活所以安全七、简化版代码返回位置结构体有点难理解如果觉得指针参数太绕可以封装成结构体#define_CRT_SECURE_NO_WARNINGS#includestdio.h#defineROWS4#defineCOLS4// 定义结果结构体typedefstruct{introw;// 行索引-1表示未找到intcol;// 列索引-1表示未找到intfound;// 1找到0未找到}Result;//结构体的别名创建结构体变量时不需要 struct 结构体//第二种定义方式/*struct Result{ int row; int col; int found; // 是否找到 } 创建变量时要使用 struct Result r {-1,-1,0};*/// 查找函数从右上角开始Resultfind_in_matrix(intmatrix[][COLS],introws,intcols,inttarget){Result r{-1,-1,0};// 默认未找到-1指无效的位置inti0,jcols-1;// 从右上角开始while(irowsj0){if(matrix[i][j]target){r.rowi;r.colj;r.found1;returnr;//返回ij位置和是否找到了}elseif(matrix[i][j]target)j--;// 向左移动elsei;// 向下移动}returnr;}// 打印结果voidprint_result(Result r,inttarget){if(r.found)//先检查是否找到了printf(✅ 找到 %d位置 [%d][%d]\n,target,r.row,r.col);elseprintf(❌ 未找到 %d\n,target);}intmain(){// 杨氏矩阵行递增列递增intmatrix[ROWS][COLS]{{1,3,5,7},{2,4,6,8},{3,5,7,9},{4,6,8,10}};inttarget0;printf(输入查找目标\n);scanf(%d,target);// 测试Result rfind_in_matrix(matrix,ROWS,COLS,target);//r的结果包括是否有目标若有则包括目标位置print_result(r,6);return0;}八、核心知识点速查知识点结论起始位置右上角 ✅ / 左下角 ✅移动规则target 当前值 → 左移target 当前值 → 下移为什么右上角左边小、下边大方向唯一左上角为什么不行右边和下边都大方向不唯一指针参数会释放吗不会修改的是 main 中的变量九、总结方面要点核心思想从右上角出发利用行列递增特性每次排除一行或一列关键技巧选一大一小的对角位置作为起点指针要点传入row/col函数内部*row修改外部变量安全不留坑⚡一句话总结从右上角开始利用左边小、下边大的特性每次排除一行或一列快速锁定目标