LeetCode 3643.子矩阵垂直翻转算法解析

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. 第1步：l=0, r=2，交换第0行和第2行

   [9,10,11] [5, 6, 7] [1, 2, 3]

2. 第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)，只使用常数额外空间

关键要点

1. 子矩阵定位：通过(x, y)定位左上角，通过k确定边长
2. 垂直翻转逻辑：只交换行，不交换列
3. 边界处理：r = x + k - 1确保指针指向有效行索引
4. 原地操作：直接修改原矩阵，无需额外空间

注意事项

• 该函数假设子矩阵是正方形（k×k）
• 函数会直接修改原矩阵，如果不想修改原矩阵，需要先进行深拷贝
• 参数x, y必须确保子矩阵在grid范围内

总结

本题通过简单的双指针方法实现了子矩阵的垂直翻转操作，代码简洁高效。理解这个算法有助于掌握二维数组的区间操作技巧。