企业官网建设流程全解析

杨氏矩阵查找

一、问题描述

在一个矩阵中查找某个数字是否存在，该矩阵满足：

• 每行从左到右递增
• 每列从上到下递增

像这样：

1 3 5 7 2 4 6 8 3 5 7 9 4 6 8 10

这种矩阵称为杨氏矩阵（Young Tableau），任务是在其中快速定位目标值。

二、核心解法：从右上角开始

算法步骤

1. 从矩阵的右上角开始
2. target == 当前值→ ✅ 找到了
3. target < 当前值→ 向左移动（排除当前列）
4. target > 当前值→ 向下移动（排除当前行）
5. 重复直到找到或越界

动画模拟

以查找target = 6为例：

起点 → 右上角 7 6 < 7 → 左移（排除第4列） ↓ 1 3 5 [7] ← 第1步：7>6，左移 2 4 6 8 3 5 7 9 4 6 8 10 1 3 [5] 7 ← 第2步：5<6，下移 2 4 6 8 3 5 7 9 4 6 8 10 1 3 5 7 2 4 [6] 8 ← 第3步：6==6，找到！✅ 3 5 7 9 4 6 8 10 位置：[1][2]

为什么从右上角？

右上角元素具有唯一的方向判断：

往左 → 元素变小 往下 → 元素变大 target > 当前值 → 只能往下走（排除当前行） target < 当前值 → 只能往左走（排除当前列）

🎯每次比较都能确定地排除一整行或一整列，不犹豫！

三、为什么不能从左上角？

从左上角开始的话：

往右 → 元素变大 往下 → 元素变大 target > 当前值 → 往右？还是往下？😵 两个方向都有可能 无法确定唯一路径！

结论：左上角和右下角都不可用，因为两个方向同大同小，路径不唯一。

四、四个起始位置对比

🧠记忆技巧：选对角的两个位置（右上 / 左下），一边大一边小，方向才唯一。

五、完整代码实现

#include<stdio.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){inti=0;// 从第 0 行开始intj=cols-1;// 从最后一列开始（右上角）while(i<rows&&j>=0){if(matrix[i][j]==target){*row=i;// 记录找到的位置*col=j;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}};inttarget=6;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) 快得多！

六、指针参数详解（⚠️ 重要！）

为什么用int* row, int* col？

intfind_in_matrix(...,int*row,int*col)

• row和col是指针参数，存储main()中变量的地址
• 通过*row = i和*col = j可以直接修改main()中的变量
• 函数返回值已被用来表示"是否找到"，位置信息通过指针传出

函数结束后，修改的值会被释放吗？

答案：不会！✅

内存图解

main() 中: int row, col; // row 在地址 0x100，col 在地址 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){intlocal=10;*p=&local;// ❌ 局部变量地址传出！}// local 被释放 → 外部拿到野指针，功能失效// 本题中安全的原因：// row 和 col 指向的是 main() 中的变量，// 这些变量在 main() 结束前都一直存活，所以安全！

七、简化版代码（返回位置结构体）有点难理解

如果觉得指针参数太绕，可以封装成结构体：

#define_CRT_SECURE_NO_WARNINGS#include<stdio.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指无效的位置inti=0,j=cols-1;// 从右上角开始while(i<rows&&j>=0){if(matrix[i][j]==target){r.row=i;r.col=j;r.found=1;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}};inttarget=0;printf("输入查找目标\n");scanf("%d",&target);// 测试Result r=find_in_matrix(matrix,ROWS,COLS,target);//r的结果包括是否有目标，若有则包括目标位置print_result(r,6);return0;}

八、核心知识点速查

九、总结

⚡一句话总结：从右上角开始，利用"左边小、下边大"的特性，每次排除一行或一列，快速锁定目标！