3643. 垂直翻转子矩阵

🎯 问题描述（来源于LeetCode）

描述：
给你一个 m x n 的整数矩阵 grid，以及三个整数 x、y 和 k。
x 和 y 表示一个 正方形子矩阵 的左上角下标，k 表示该正方形子矩阵的边长。
你的任务是垂直翻转该子矩阵的行顺序（即上下翻转），并返回更新后的矩阵。

说明：

  • 垂直翻转：子矩阵的第一行与最后一行交换，第二行与倒数第二行交换，以此类推。
  • 子矩阵外的元素保持不变。
  • 你可以直接在原矩阵上修改，也可以使用额外空间。

示例：

  • 示例 1：
1
2
3
输入: grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], x = 1, y = 0, k = 3
输出: [[1,2,3,4],[13,14,15,8],[9,10,11,12],[5,6,7,16]]
解释: 目标子矩阵为行 1-3、列 0-2。翻转前行顺序为：[5,6,7]、[9,10,11]、[13,14,15]；翻转后行顺序变为：[13,14,15]、[9,10,11]、[5,6,7]，列3保持不变。
  • 示例 2：
1
2
3
输入: grid = [[3,4,2,3],[2,3,4,2]], x = 0, y = 2, k = 2
输出: [[3,4,4,2],[2,3,2,3]]
解释: 目标子矩阵为行 0-1、列 2-3。翻转前为 [[2,3],[4,2]]，翻转后变为 [[4,2],[2,3]]。

💻 解题思路

思路：双指针逐行交换（原地修改）

算法步骤

  1. 确定子矩阵边界：
    • 顶部行：top = x
    • 底部行：bottom = x + k - 1
  2. 双指针交换行：
    • 当 top < bottom 时，进行循环：
      • 遍历子矩阵的每一列 j，范围从 y 到 y + k - 1。
      • 交换 grid[top][j] 和 grid[bottom][j] 的值。
      • 交换完成后，top 向下移动一行（top++），bottom 向上移动一行（bottom--）。
  3. 返回结果：原地修改矩阵后，直接返回 grid。

代码实现（你的代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from typing import List

class Solution:
    def reverseSubmatrix(self, grid: List[List[int]], x: int, y: int, k: int) -> List[List[int]]:
        # 初始化上下两个行指针
        l, r = x, x + k - 1
        while l < r:
            # 交换当前两行在子矩阵范围内的所有元素
            for j in range(y, y + k):
                grid[l][j], grid[r][j] = grid[r][j], grid[l][j]
            # 指针向中间移动
            l += 1
            r -= 1
        return grid

📊 性能分析

  • 时间复杂度：O(k2)O(k^2)，因为需要遍历子矩阵中一半的行（k/2k/2 行），每行有 kk 个元素需要交换。
  • 空间复杂度：O(1)O(1)，仅使用了有限的几个指针变量，在原矩阵上直接进行修改。

思考

你的解法非常经典，直接利用了双指针（或称为对撞指针）的思想。它通过同时从子矩阵的顶部和底部向中间遍历，并交换对应行的所有元素，高效地完成了垂直翻转。

优点：

  • 原地修改：没有使用额外的矩阵空间，内存效率高。
  • 逻辑清晰：代码直观地反映了“上下交换行”这一操作本质。