Medium

题目描述

给你一个大小为 m x n 的整数矩阵 grid​​​，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。

矩阵由若干层组成，如下图所示，每种颜色代表一层：

矩阵的循环轮转是通过分别循环轮转矩阵中的每一层来完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针 方向的相邻元素。一个示例轮转如下所示：

返回执行 k 次循环轮转操作后的矩阵。

示例 1：

输入：grid = [[40,10],[30,20]], k = 1
输出：[[10,20],[40,30]]
解释：上面的图片展示了矩阵在每次状态下的样子。

示例 2：

输入：grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
输出：[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
解释：上面的图片展示了矩阵在每次状态下的样子。

提示：

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 50
  • m 和 n 都是 偶数
  • 1 <= grid[i][j] <= 5000
  • 1 <= k <= 10^9

解题思路

这道题的关键是理解矩阵的层状结构以及如何对每一层进行循环轮转。

思路分析：

  1. 层的概念：矩阵可以看作由多个同心矩形层组成，最外层到最内层。对于一个 m×n 的矩阵，层数为 min(m,n)/2。

  2. 提取每层元素：对于第 i 层（从0开始），我们需要按逆时针方向提取所有元素到一个一维数组中。遍历顺序为：上边→左边→下边→右边。

  3. 循环轮转优化：由于 k 可能很大（最大10^9），直接轮转k次会超时。我们可以利用取模运算优化：对于长度为 len 的层，轮转 k 次等价于轮转 k % len 次。

  4. 重新放置元素：将轮转后的一维数组按原来的路径重新放回矩阵中。

算法步骤：

  • 遍历每一层
  • 提取当前层的所有元素到数组
  • 计算有效轮转次数（取模）
  • 对数组进行循环轮转
  • 将轮转后的元素放回原位置

时间复杂度为 O(mn)，空间复杂度为 O(min(m,n))。

代码实现

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        int layers = min(m, n) / 2;
        
        for (int layer = 0; layer < layers; layer++) {
            vector<int> elements;
            
            // 提取当前层的元素（逆时针方向）
            // 上边（从左到右）
            for (int j = layer; j < n - layer; j++) {
                elements.push_back(grid[layer][j]);
            }
            // 右边（从上到下，不包括右上角）
            for (int i = layer + 1; i < m - layer; i++) {
                elements.push_back(grid[i][n - 1 - layer]);
            }
            // 下边（从右到左，不包括右下角，且只有多行时才有下边）
            if (m - 1 - layer > layer) {
                for (int j = n - 2 - layer; j >= layer; j--) {
                    elements.push_back(grid[m - 1 - layer][j]);
                }
            }
            // 左边（从下到上，不包括左下角和左上角，且只有多列时才有左边）
            if (n - 1 - layer > layer) {
                for (int i = m - 2 - layer; i > layer; i--) {
                    elements.push_back(grid[i][layer]);
                }
            }
            
            // 计算有效轮转次数
            int len = elements.size();
            int rotations = k % len;
            
            // 轮转数组
            vector<int> rotated(elements.begin() + rotations, elements.end());
            rotated.insert(rotated.end(), elements.begin(), elements.begin() + rotations);
            
            // 将轮转后的元素放回原位置
            int idx = 0;
            // 上边
            for (int j = layer; j < n - layer; j++) {
                grid[layer][j] = rotated[idx++];
            }
            // 右边
            for (int i = layer + 1; i < m - layer; i++) {
                grid[i][n - 1 - layer] = rotated[idx++];
            }
            // 下边
            if (m - 1 - layer > layer) {
                for (int j = n - 2 - layer; j >= layer; j--) {
                    grid[m - 1 - layer][j] = rotated[idx++];
                }
            }
            // 左边
            if (n - 1 - layer > layer) {
                for (int i = m - 2 - layer; i > layer; i--) {
                    grid[i][layer] = rotated[idx++];
                }
            }
        }
        
        return grid;
    }
};

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        layers = min(m, n) // 2
        
        for layer in range(layers):
            elements = []
            
            # 提取当前层的元素（逆时针方向）
            # 上边（从左到右）
            for j in range(layer, n - layer):
                elements.append(grid[layer][j])
            # 右边（从上到下，不包括右上角）
            for i in range(layer + 1, m - layer):
                elements.append(grid[i][n - 1 - layer])
            # 下边（从右到左，不包括右下角）
            if m - 1 - layer > layer:
                for j in range(n - 2 - layer, layer - 1, -1):
                    elements.append(grid[m - 1 - layer][j])
            # 左边（从下到上，不包括左下角和左上角）
            if n - 1 - layer > layer:
                for i in range(m - 2 - layer, layer, -1):
                    elements.append(grid[i][layer])
            
            # 计算有效轮转次数并轮转
            rotations = k % len(elements)
            elements = elements[rotations:] + elements[:rotations]
            
            # 将轮转后的元素放回原位置
            idx = 0
            # 上边
            for j in range(layer, n - layer):
                grid[layer][j] = elements[idx]
                idx += 1
            # 右边
            for i in range(layer + 1, m - layer):
                grid[i][n - 1 - layer] = elements[idx]
                idx += 1
            # 下边
            if m - 1 - layer > layer:
                for j in range(n - 2 - layer, layer - 1, -1):
                    grid[m - 1 - layer][j] = elements[idx]
                    idx += 1
            # 左边
            if n - 1 - layer > layer:
                for i in range(m - 2 - layer, layer, -1):
                    grid[i][layer] = elements[idx]
                    idx += 1
        
        return grid

public class Solution {
    public int[][] RotateGrid(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        int layers = Math.Min(m, n) / 2;
        
        for (int layer = 0; layer < layers; layer++) {
            var elements = new List<int>();
            
            // 提取当前层的元素（逆时针方向）
            // 上边（从左到右）
            for (int j = layer; j < n - layer; j++) {
                elements.Add(grid[layer][j]);
            }
            // 右边（从上到下，不包括右上角）
            for (int i = layer + 1; i < m - layer; i++) {
                elements.Add(grid[i][n - 1 - layer]);
            }
            // 下边（从右到左，不包括右下角）
            if (m - 1 - layer > layer) {
                for (int j = n - 2 - layer; j >= layer; j--) {
                    elements.Add(grid[m - 1 - layer][j]);
                }
            }
            // 左边（从下到上，不包括左下角和左上角）
            if (n - 1 - layer > layer) {
                for (int i = m - 2 - layer; i > layer; i--) {
                    elements.Add(grid[i][layer]);
                }
            }
            
            // 计算有效轮转次数并轮转
            int len = elements.Count;
            int rotations = k % len;
            var rotated = new List<int>();
            rotated.AddRange(elements.GetRange(rotations, len - rotations));
            rotated.AddRange(elements.GetRange(0, rotations));
            
            // 将轮转后的元素放回原位置
            int idx = 0;
            // 上边
            for (int j = layer; j < n - layer; j++) {
                grid[layer][j] = rotated[idx++];
            }
            // 右边
            for (int i = layer + 1; i < m - layer; i++) {
                grid[i][n - 1 - layer] = rotated[idx++];
            }
            // 下边
            if (m - 1 - layer > layer) {
                for (int j = n - 2 - layer; j >= layer; j--) {
                    grid[m - 1 - layer][j] = rotated[idx++];
                }
            }
            // 左边
            if (n - 1 - layer > layer) {
                for (int i = m - 2 - layer; i > layer; i--) {
                    grid[i][layer] = rotated[idx++];
                }
            }
        }
        
        return grid;
    }
}

var rotateGrid = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    const layers = Math.min(m, n) / 2;
    
    for (let layer = 0; layer < layers; layer++) {
        const elements = [];
        
        // 提取当前层的元素（逆时针方向）
        // 上边（从左到右）
        for (let j = layer; j < n - layer; j++) {
            elements.push(grid[layer][j]);
        }
        // 右边（从上到下，不包括右上角）
        for (let i = layer + 1; i < m - layer; i++) {
            elements.push(grid[i][n - 1 - layer]);
        }
        // 下边（从右到左，不包括右下角）
        if (m - 1 - layer > layer) {
            for (let j = n - 2 - layer; j >= layer; j--) {
                elements.push(grid[m - 1 - layer][j]);
            }
        }
        // 左边（从下到上，不包括左下角和左上角）
        if (n - 1 - layer > layer) {
            for (let i = m - 2 - layer; i > layer; i--) {
                elements.push(grid[i][layer]);
            }
        }
        
        // 计算有效轮转次数并轮转
        const len = elements.length;
        const rotations = k % len;
        const rotated = elements.slice(rotations).concat(elements.slice(0, rotations));
        
        // 将轮转后的元素放回原位置
        let idx = 0;
        // 上边
        for (let j = layer; j < n - layer; j++) {
            grid[layer][j] = rotated[idx++];
        }
        // 右边
        for (let i = layer + 1; i < m - layer; i++) {
            grid[i][n - 1 - layer] = rotated[idx++];
        }
        // 下边
        if (m - 1 - layer > layer) {
            for (let j = n - 2 - layer; j >= layer; j--) {
                grid[m - 1 - layer][j] = rotated[idx++];
            }
        }
        // 左边
        if (n - 1 - layer > layer) {
            for (let i = m - 2 - layer; i > layer; i--) {
                grid[i][layer] = rotated[idx++];
            }
        }
    }
    
    return grid;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(m × n)
空间复杂度O(min(m, n))
  • 时间复杂度：O(m × n)，需要遍历矩阵中的每个元素恰好常数次
  • 空间复杂度：O(min(m, n))，需要额外空间存储每一层的元素，最大层的元素数量为 O(m + n)