登录利用方向向量简化代码，O(1) 空间优化（Python/Java/C++/Go）
本题是模拟题，由于每一圈互相独立，可以分别处理。
对于每一圈：
- 从左上角开始，顺时针遍历这一圈，把遍历到的元素记录到一个数组 $a$ 中。
- 把 $a$ 循环左移 $k\bmod N$ 次，其中 $N$ 是数组 $a$ 的长度。这是因为，循环左移 $N$ 次等同于没有左移，循环左移 $N+1$ 次等同于循环左移 $1$ 次，依此类推，循环左移 $k$ 次等同于循环左移 $k\bmod N$ 次。
- 把 $a$ 中元素按照步骤 1 中的顺序，重新填回 $\textit{grid}$。
对于步骤 1，可以仿照 54. 螺旋矩阵 的 方法二，使用一个方向向量数组分别表示顺时针的右、下、左、上。对于最外圈，分别移动 $n-1,m-1,n-1,m-1$ 次；对于次外圈，分别移动 $n-3,m-3,n-3,m-3$ 次；依此类推。
DIRS = (0, 1), (1, 0), (0, -1), (-1, 0) # 右下左上
class Solution:
def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
m0, n0 = len(grid), len(grid[0])
# 从外到内枚举圈
for i in range(min(m0, n0) // 2):
m, n = m0 - i * 2, n0 - i * 2 # 这一圈的行数和列数
x, y = i, i # 这一圈的左上角
a = []
for dx, dy in DIRS:
for _ in range(n - 1):
a.append(grid[x][y])
x += dx
y += dy
m, n = n, m # 见 54. 螺旋矩阵 我的题解
shift = k % len(a)
a = a[shift:] + a[:shift]
# 注意此时 (x, y) 又回到了左上角
j = 0
for dx, dy in DIRS:
for _ in range(n - 1):
grid[x][y] = a[j]
j += 1
x += dx
y += dy
m, n = n, m
return grid
class Solution {
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
public int[][] rotateGrid(int[][] grid, int k) {
int m0 = grid.length, n0 = grid[0].length;
List<Integer> a = new ArrayList<>((m0 + n0 - 2) * 2); // 预分配空间
// 从外到内枚举圈
for (int i = 0; i < Math.min(m0, n0) / 2; i++) {
int m = m0 - i * 2, n = n0 - i * 2; // 这一圈的行数和列数
int x = i, y = i; // 这一圈的左上角
a.clear();
for (int[] dir : DIRS) {
for (int t = 0; t < n - 1; t++) {
a.add(grid[x][y]);
x += dir[0];
y += dir[1];
}
int tmp = m; // 见 54. 螺旋矩阵 我的题解
m = n;
n = tmp;
}
int shift = k % a.size();
Collections.rotate(a, -shift);
// 注意此时 (x, y) 又回到了左上角
int j = 0;
for (int[] dir : DIRS) {
for (int t = 0; t < n - 1; t++) {
grid[x][y] = a.get(j++);
x += dir[0];
y += dir[1];
}
int temp = m;
m = n;
n = temp;
}
}
return grid;
}
}
class Solution {
static constexpr int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
public:
vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
int m0 = grid.size(), n0 = grid[0].size();
vector<int> a;
a.reserve((m0 + n0 - 2) * 2); // 预分配空间
// 从外到内枚举圈
for (int i = 0; i < min(m0, n0) / 2; i++) {
int m = m0 - i * 2, n = n0 - i * 2; // 这一圈的行数和列数
int x = i, y = i; // 这一圈的左上角
a.resize(0);
for (auto& [dx, dy] : DIRS) {
for (int t = 0; t < n - 1; t++) {
a.push_back(grid[x][y]);
x += dx;
y += dy;
}
swap(m, n); // 见 54. 螺旋矩阵 我的题解
}
int shift = k % a.size();
ranges::rotate(a, a.begin() + shift);
// 注意此时 (x, y) 又回到了左上角
int j = 0;
for (auto& [dx, dy] : DIRS) {
for (int t = 0; t < n - 1; t++) {
grid[x][y] = a[j++];
x += dx;
y += dy;
}
swap(m, n);
}
}
return grid;
}
};
var dirs = [4][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 右下左上
func rotateGrid(grid [][]int, k int) [][]int {
m0, n0 := len(grid), len(grid[0])
a := make([]int, 0, (m0+n0-2)*2) // 预分配空间
// 从外到内枚举圈
for i := range min(m0, n0) / 2 {
m, n := m0-i*2, n0-i*2 // 这一圈的行数和列数
x, y := i, i // 这一圈的左上角
a = a[:0]
for _, dir := range dirs {
for range n - 1 {
a = append(a, grid[x][y])
x += dir[0]
y += dir[1]
}
m, n = n, m // 见 54. 螺旋矩阵 我的题解
}
shift := k % len(a)
a = append(a[shift:], a[:shift]...)
// 注意此时 (x, y) 又回到了左上角
j := 0
for _, dir := range dirs {
for range n - 1 {
grid[x][y] = a[j]
j++
x += dir[0]
y += dir[1]
}
m, n = n, m
}
}
return grid
}
复杂度分析
- 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。
- 空间复杂度：$\mathcal{O}(m+n)$。
空间优化
利用 189. 轮转数组 的技巧，可以做到 $\mathcal{O}(1)$ 空间。详见 我的题解。
class Solution:
def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
m0, n0 = len(grid), len(grid[0])
# 从外到内枚举圈
for i in range(min(m0, n0) // 2):
m, n = m0 - i * 2 - 1, n0 - i * 2 - 1 # 注意这里减一了
# 返回这一圈顺时针下标 p 对应 grid 的位置 (x, y)
def index(p: int) -> Tuple[int, int]:
# 左上角在 (i, i)
if p < n:
return i, i + p
if p < n + m:
return i + p - n, i + n
if p < n * 2 + m:
return i + m, i - p + n * 2 + m
return i - p + (n + m) * 2, i
def reverse(l: int, r: int) -> None:
while l < r:
x1, y1 = index(l)
x2, y2 = index(r)
grid[x1][y1], grid[x2][y2] = grid[x2][y2], grid[x1][y1]
l += 1
r -= 1
# 189. 轮转数组（改成向左轮转）
size = (m + n) * 2
shift = k % size
reverse(0, shift - 1)
reverse(shift, size - 1)
reverse(0, size - 1)
return grid
class Solution {
public int[][] rotateGrid(int[][] grid, int k) {
int m0 = grid.length, n0 = grid[0].length;
// 从外到内枚举圈
for (int i = 0; i < Math.min(m0, n0) / 2; i++) {
int m = m0 - i * 2 - 1, n = n0 - i * 2 - 1; // 注意这里减一了
// 189. 轮转数组（改成向左轮转）
int size = (m + n) * 2;
int shift = k % size;
reverse(grid, i, m, n, 0, shift - 1);
reverse(grid, i, m, n, shift, size - 1);
reverse(grid, i, m, n, 0, size - 1);
}
return grid;
}
private void reverse(int[][] grid, int i, int m, int n, int l, int r) {
while (l < r) {
int[] p1 = index(i, m, n, l);
int[] p2 = index(i, m, n, r);
int x1 = p1[0], y1 = p1[1];
int x2 = p2[0], y2 = p2[1];
int tmp = grid[x1][y1];
grid[x1][y1] = grid[x2][y2];
grid[x2][y2] = tmp;
l++;
r--;
}
}
private int[] index(int i, int m, int n, int p) {
// 左上角在 (i, i)
if (p < n) {
return new int[]{i, i + p};
}
if (p < n + m) {
return new int[]{i + p - n, i + n};
}
if (p < n * 2 + m) {
return new int[]{i + m, i - p + n * 2 + m};
}
return new int[]{i - p + (n + m) * 2, i};
}
}
class Solution {
public:
vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
int m0 = grid.size(), n0 = grid[0].size();
// 从外到内枚举圈
for (int i = 0; i < min(m0, n0) / 2; i++) {
int m = m0 - i * 2 - 1, n = n0 - i * 2 - 1; // 注意这里减一了
// 返回这一圈顺时针下标 p 对应 grid 的位置 (x, y)
auto index = [&](int p) -> pair<int, int> {
// 左上角在 (i, i)
if (p < n) {
return {i, i + p};
}
if (p < n + m) {
return {i + p - n, i + n};
}
if (p < n * 2 + m) {
return {i + m, i - p + n * 2 + m};
}
return {i - p + (n + m) * 2, i};
};
auto reverse = [&](int l, int r) {
while (l < r) {
auto [x1, y1] = index(l);
auto [x2, y2] = index(r);
swap(grid[x1][y1], grid[x2][y2]);
l++;
r--;
}
};
// 189. 轮转数组（改成向左轮转）
int size = (m + n) * 2;
int shift = k % size;
reverse(0, shift - 1);
reverse(shift, size - 1);
reverse(0, size - 1);
}
return grid;
}
};
func rotateGrid(grid [][]int, k int) [][]int {
m0, n0 := len(grid), len(grid[0])
// 从外到内枚举圈
for i := range min(m0, n0) / 2 {
m, n := m0-i*2-1, n0-i*2-1 // 注意这里减一了
// 返回这一圈顺时针下标 p 对应 grid 的位置 (x, y)
index := func(p int) (x, y int) {
// 左上角在 (i, i)
if p < n {
return i, i + p
}
if p < n+m {
return i + p - n, i + n
}
if p < n*2+m {
return i + m, i - p + n*2 + m
}
return i - p + (n+m)*2, i
}
reverse := func(l, r int) {
for l < r {
x1, y1 := index(l)
x2, y2 := index(r)
grid[x1][y1], grid[x2][y2] = grid[x2][y2], grid[x1][y1]
l++
r--
}
}
// 189. 轮转数组（改成向左轮转）
size := (m + n) * 2
shift := k % size
reverse(0, shift-1)
reverse(shift, size-1)
reverse(0, size-1)
}
return grid
}
复杂度分析
- 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\textit{grid}$ 的行数和列数。
- 空间复杂度：$\mathcal{O}(1)$。
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
