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

LeetCode 3643.子矩阵垂直翻转算法解析题目描述给定一个二维矩阵grid和四个参数(x, y, k)实现一个函数将矩阵中以(x, y)为左上角、边长为k的正方形子矩阵进行上下翻转垂直镜像翻转。算法思路本题的核心是实现子矩阵的垂直翻转操作。垂直翻转即将子矩阵的第1行与第k行交换第2行与第k-1行交换以此类推直到中间行。实现方法采用双指针法设置两个指针l上边界和r下边界初始分别指向子矩阵的第一行和最后一行当l r时交换这两行的所有元素然后lr--继续交换直到两指针相遇代码实现classSolution{public:vectorvectorintreverseSubmatrix(vectorvectorintgrid,intx,inty,intk){intlx,rxk-1;// 设置上下边界指针while(lr){// 当未到达中间时for(intjy;jyk;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步l0, r2交换第0行和第2行[9,10,11] [5, 6, 7] [1, 2, 3]第2步l1, r1循环结束最终结果[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范围内总结本题通过简单的双指针方法实现了子矩阵的垂直翻转操作代码简洁高效。理解这个算法有助于掌握二维数组的区间操作技巧。