Easy

题目描述

给你一个 m x n 的整数矩阵 grid，以及三个整数 x、y 和 k。

整数 x 和 y 表示正方形子矩阵左上角的行索引和列索引，整数 k 表示正方形子矩阵的大小（边长）。

你的任务是通过垂直反转行的顺序来翻转子矩阵。

返回更新后的矩阵。

示例 1：

输入：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]]

示例 2：

输入：grid = [[3,4,2,3],[2,3,4,2]], x = 0, y = 2, k = 2

输出：[[3,4,4,2],[2,3,2,3]]

约束条件：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 100
  • 0 <= x < m
  • 0 <= y < n
  • 1 <= k <= min(m - x, n - y)

解题思路

这道题要求我们对指定的正方形子矩阵进行垂直翻转，即反转其行的顺序。

解题思路

核心思想：使用双指针技术，从子矩阵的顶部和底部同时开始，逐行交换对应位置的元素。

具体步骤：

  1. 确定子矩阵的边界：从位置 (x, y) 开始，大小为 k x k
  2. 设置两个指针：top 指向子矩阵的第一行，bottom 指向子矩阵的最后一行
  3. 当 top < bottom 时，交换这两行在子矩阵范围内的所有元素
  4. 移动指针：top++，bottom--，继续交换直到指针相遇

时间复杂度优化：每个元素最多被访问一次，整个过程只需要 O(k²) 的时间复杂度。

推荐解法：双指针法是最直观且高效的解法，代码简洁易懂，符合题目提示。

代码实现

class Solution {
public:
    vector<vector<int>> reverseSubmatrix(vector<vector<int>>& grid, int x, int y, int k) {
        int top = x, bottom = x + k - 1;
        
        while (top < bottom) {
            for (int j = y; j < y + k; j++) {
                swap(grid[top][j], grid[bottom][j]);
            }
            top++;
            bottom--;
        }
        
        return grid;
    }
};

class Solution:
    def reverseSubmatrix(self, grid: List[List[int]], x: int, y: int, k: int) -> List[List[int]]:
        top, bottom = x, x + k - 1
        
        while top < bottom:
            for j in range(y, y + k):
                grid[top][j], grid[bottom][j] = grid[bottom][j], grid[top][j]
            top += 1
            bottom -= 1
        
        return grid

public class Solution {
    public int[][] ReverseSubmatrix(int[][] grid, int x, int y, int k) {
        int top = x, bottom = x + k - 1;
        
        while (top < bottom) {
            for (int j = y; j < y + k; j++) {
                int temp = grid[top][j];
                grid[top][j] = grid[bottom][j];
                grid[bottom][j] = temp;
            }
            top++;
            bottom--;
        }
        
        return grid;
    }
}

var reverseSubmatrix = function(grid, x, y, k) {
    let top = x, bottom = x + k - 1;
    
    while (top < bottom) {
        for (let j = y; j < y + k; j++) {
            [grid[top][j], grid[bottom][j]] = [grid[bottom][j], grid[top][j]];
        }
        top++;
        bottom--;
    }
    
    return grid;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k²) - 需要交换子矩阵中的每个元素，总共 k² 个元素
空间复杂度O(1) - 只使用常数额外空间，原地修改矩阵