LeetCode 3643.子矩阵垂直翻转算法解析
题目描述
给定一个二维矩阵grid和四个参数(x, y, k)，实现一个函数，将矩阵中以(x, y)为左上角、边长为k的正方形子矩阵进行上下翻转（垂直镜像翻转）。
算法思路
本题的核心是实现子矩阵的垂直翻转操作。垂直翻转即将子矩阵的第1行与第k行交换，第2行与第k-1行交换，以此类推，直到中间行。
实现方法
采用双指针法：
- 设置两个指针
l（上边界）和r（下边界），初始分别指向子矩阵的第一行和最后一行 - 当
l < r时，交换这两行的所有元素 - 然后
l++，r--，继续交换直到两指针相遇
代码实现
classSolution{public:vector<vector<int>>reverseSubmatrix(vector<vector<int>>&grid,intx,inty,intk){intl=x,r=x+k-1;// 设置上下边界指针while(l<r){// 当未到达中间时for(intj=y;j<y+k;j++)// 交换当前两行的所有列swap(grid[l][j],grid[r][j]);l++;// 上边界下移r--;// 下边界上移}returngrid;}};算法图解
示例演示
假设输入矩阵：
grid = [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12], [13,14,15,16] ] 调用 reverseSubmatrix(grid, 0, 0, 3)子矩阵范围（左上角(0,0)，边长3）：
[1, 2, 3] [5, 6, 7] [9,10,11]执行过程：
- 第1步：
l=0, r=2，交换第0行和第2行[9,10,11] [5, 6, 7] [1, 2, 3] - 第2步：
l=1, r=1，循环结束
最终结果：
[9,10,11,4] [5, 6, 7,8] [1, 2, 3,12] [13,14,15,16]复杂度分析
- 时间复杂度：O(k²)，需要遍历子矩阵中所有元素一次
- 空间复杂度：O(1)，只使用常数额外空间
关键要点
- 子矩阵定位：通过
(x, y)定位左上角，通过k确定边长 - 垂直翻转逻辑：只交换行，不交换列
- 边界处理：
r = x + k - 1确保指针指向有效行索引 - 原地操作：直接修改原矩阵，无需额外空间
注意事项
- 该函数假设子矩阵是正方形（k×k）
- 函数会直接修改原矩阵，如果不想修改原矩阵，需要先进行深拷贝
- 参数
x, y必须确保子矩阵在grid范围内
总结
本题通过简单的双指针方法实现了子矩阵的垂直翻转操作，代码简洁高效。理解这个算法有助于掌握二维数组的区间操作技巧。
