循环轮转矩阵 图解题解
这道题到底在问什么
- 输入
- grid=[[40,10],[30,20]], k=1
- 输出
- [[10,20],[40,30]]
- 输入
- 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]]
最优解:一步一步想明白
- 3记牢这一句:把一圈数拆成一条链,链头砍 k 个接到链尾,再摆回去。转多少次都不用真的一格一格挪,一次取模就搞定。下面从最外层开始。
- 4两层同心方环先给整张网格分层。橙色的是外层,一圈 12 个数;绿色的是内层,一圈 4 个数。行列都是偶数,所以每一层都是完整的一圈,没有落单的中心格。轮转的时候两层各转各的,咱们先攻外层这一圈。
- 5外层开工锁定外层这一圈,一共 12 个格子。我们从左上角 (0,0) 出发,按上行、右列、下行、左列的顺时针方向,把这一圈的数依次抄下来,排成一条链。
- 6读第 1 边沿着上行,左到右把这几个数抄下来:1、2、3。它们进到链里的顺序,就是它们在环上的顺序。
- 7拆成一条链把刚抄的接到链尾,现在这条链有 3 个数了。紫色是刚放进来的那个。继续沿着环往下抄。
- 8读第 2 边沿着右列,上到下把这几个数抄下来:4、8、12。它们进到链里的顺序,就是它们在环上的顺序。
- 9拆成一条链把刚抄的接到链尾,现在这条链有 6 个数了。紫色是刚放进来的那个。继续沿着环往下抄。
- 10读第 3 边沿着下行,右到左把这几个数抄下来:16、15、14。它们进到链里的顺序,就是它们在环上的顺序。
- 11拆成一条链把刚抄的接到链尾,现在这条链有 9 个数了。紫色是刚放进来的那个。继续沿着环往下抄。
- 12读第 4 边沿着左列,下到上把这几个数抄下来:13、9、5。它们进到链里的顺序,就是它们在环上的顺序。
- 13拆成一条链把刚抄的接到链尾,现在这条链有 12 个数了。紫色是刚放进来的那个。一整圈全下来了,链就集齐了,接下来对它做轮转。
- 14k 取模轮转 2 次,不用真挪 2 回。链长 12,2 对 12 取模还是 2,所以只要把链头的 2 个数,也就是标红的 1 和 2,整体搬到链尾就行。
- 15链头搬到链尾搬完就是这条新链:原来的链头 1 和 2 跑到了最后面(绿色),其余的数整体往前顶了 2 位。这就是这一层轮转 2 次之后该有的排布,接下来按原位置把它摆回环里。
- 16摆回环里按刚才抄链的同一条路线,把新链的数依次摆回上行这几格:3、4、8。位置一一对应,一个不差。
- 17摆回环里按刚才抄链的同一条路线,把新链的数依次摆回右列这几格:12、16、15。位置一一对应,一个不差。
- 18摆回环里按刚才抄链的同一条路线,把新链的数依次摆回下行这几格:14、13、9。位置一一对应,一个不差。
- 19摆回环里按刚才抄链的同一条路线,把新链的数依次摆回左列这几格:5、1、2。位置一一对应,一个不差。
- 20外层完成外层一圈全部摆回,这一层就转好了。可以对照一下第一行,已经从 1、2、3、4 变成了 3、4、8、12。外层收工,接着钻进内层。
- 21内层开工外层已经转好了,标成绿色定住。现在轮到内层这一圈,一共 4 个格子。同样从它的左上角 (1,1) 起,顺时针把这 4 个数抄成一条链。
- 22读第 1 边沿着上行与右列把这几个数抄下来:6、7。它们进到链里的顺序,就是它们在环上的顺序。
- 23拆成一条链把刚抄的接到链尾,现在这条链有 2 个数了。紫色是刚放进来的那个。继续沿着环往下抄。
- 24读第 2 边沿着下行与左列把这几个数抄下来:11、10。它们进到链里的顺序,就是它们在环上的顺序。
- 25拆成一条链把刚抄的接到链尾,现在这条链有 4 个数了。紫色是刚放进来的那个。一整圈全下来了,链就集齐了,接下来对它做轮转。
- 26k 取模轮转 2 次,不用真挪 2 回。链长 4,2 对 4 取模还是 2,所以只要把链头的 2 个数,也就是标红的 6 和 7,整体搬到链尾就行。
- 27链头搬到链尾搬完就是这条新链:原来的链头 6 和 7 跑到了最后面(绿色),其余的数整体往前顶了 2 位。这就是这一层轮转 2 次之后该有的排布,接下来按原位置把它摆回环里。
- 28摆回环里按刚才抄链的同一条路线,把新链的数依次摆回上行与右列这几格:11、10。位置一一对应,一个不差。
- 29摆回环里按刚才抄链的同一条路线,把新链的数依次摆回下行与左列这几格:6、7。位置一一对应,一个不差。
- 30内层完成内层这一圈也摆回原位,两层都转完了。整张矩阵的最终形态就出来了。
- 31答案两层都转好,最终矩阵就是这张网格,和题面给的答案一模一样。回头看整套流程,核心就三步:拆环成链、链头砍 k 个接到链尾、按原位置摆回去。层与层之间互不影响,分开处理就好。
⚠️ 容易写错的地方
✗ 错:老老实实把每层转 k 次
✓ 对:k 先对环长取模,一步到位
k 最大能到十的九次方,真转 k 次会超时。转一整圈等于没转,取模后只需搬动余数那几个
✗ 错:取环和回填用了不同的绕行方向
✓ 对:两趟必须用完全相同的位置顺序
抄链和摆回是逆运算,只有走同一条路线,链上第 x 个才对应环上第 x 个位置,否则数值会错位
✗ 错:给整个矩阵只拆一条大链一起转
✓ 对:必须一层一层分开拆、分开转
不同层是相互独立的环,混在一起转会让内外层的数串到彼此的位置上,结果全乱
✗ 错:四段循环边界写成闭区间、两端拐角都取
✓ 对:每段用半开边界错开拐角,每个拐角只归一条边、只抄一次
四条边共用四个拐角,若每段都取到两端端点,拐角会被抄两遍,链长和位置都对不上
完整代码(Python / C++ / Java)
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
def rotate(p: int, k: int):
nums = []
for j in range(p, n - p - 1):
nums.append(grid[p][j])
for i in range(p, m - p - 1):
nums.append(grid[i][n - p - 1])
for j in range(n - p - 1, p, -1):
nums.append(grid[m - p - 1][j])
for i in range(m - p - 1, p, -1):
nums.append(grid[i][p])
k %= len(nums)
if k == 0:
return
nums = nums[k:] + nums[:k]
k = 0
for j in range(p, n - p - 1):
grid[p][j] = nums[k]
k += 1
for i in range(p, m - p - 1):
grid[i][n - p - 1] = nums[k]
k += 1
for j in range(n - p - 1, p, -1):
grid[m - p - 1][j] = nums[k]
k += 1
for i in range(m - p - 1, p, -1):
grid[i][p] = nums[k]
k += 1
m, n = len(grid), len(grid[0])
for p in range(min(m, n) >> 1):
rotate(p, k)
return gridC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
auto rotate = [&](int p, int k) {
vector<int> nums;
for (int j = p; j < n - p - 1; ++j) {
nums.push_back(grid[p][j]);
}
for (int i = p; i < m - p - 1; ++i) {
nums.push_back(grid[i][n - p - 1]);
}
for (int j = n - p - 1; j > p; --j) {
nums.push_back(grid[m - p - 1][j]);
}
for (int i = m - p - 1; i > p; --i) {
nums.push_back(grid[i][p]);
}
int l = nums.size();
k %= l;
if (k == 0) {
return;
}
for (int j = p; j < n - p - 1; ++j) {
grid[p][j] = nums[k++ % l];
}
for (int i = p; i < m - p - 1; ++i) {
grid[i][n - p - 1] = nums[k++ % l];
}
for (int j = n - p - 1; j > p; --j) {
grid[m - p - 1][j] = nums[k++ % l];
}
for (int i = m - p - 1; i > p; --i) {
grid[i][p] = nums[k++ % l];
}
};
for (int p = 0; p < min(m, n) / 2; ++p) {
rotate(p, k);
}
return grid;
}
};Java
import java.util.*;
class Solution {
private int m;
private int n;
private int[][] grid;
public int[][] rotateGrid(int[][] grid, int k) {
m = grid.length;
n = grid[0].length;
this.grid = grid;
for (int p = 0; p < Math.min(m, n) / 2; ++p) {
rotate(p, k);
}
return grid;
}
private void rotate(int p, int k) {
List<Integer> nums = new ArrayList<>();
for (int j = p; j < n - p - 1; ++j) {
nums.add(grid[p][j]);
}
for (int i = p; i < m - p - 1; ++i) {
nums.add(grid[i][n - p - 1]);
}
for (int j = n - p - 1; j > p; --j) {
nums.add(grid[m - p - 1][j]);
}
for (int i = m - p - 1; i > p; --i) {
nums.add(grid[i][p]);
}
int l = nums.size();
k %= l;
if (k == 0) {
return;
}
for (int j = p; j < n - p - 1; ++j) {
grid[p][j] = nums.get(k++ % l);
}
for (int i = p; i < m - p - 1; ++i) {
grid[i][n - p - 1] = nums.get(k++ % l);
}
for (int j = n - p - 1; j > p; --j) {
grid[m - p - 1][j] = nums.get(k++ % l);
}
for (int i = m - p - 1; i > p; --i) {
grid[i][p] = nums.get(k++ % l);
}
}
}复杂度
时间
O(m·n)
所有层的环加起来正好覆盖矩阵的每一个格子。取环、轮转、回填每个格子都只被读写常数次,k 通过一次取模压成不超过环长,不会真的转 k 遍。所以总时间随格子数线性增长,与 m 乘 n 成正比
空间
O(max(m,n))
按峰值算。每次只为当前这一层开一条链 nums,最外层的环最长,长度是 2 乘 m 加 2 乘 n 再减 4 的量级,即 O(m 加 n)。逐层处理时旧链可以复用,峰值就是最长的那条环,不额外随面积增长
看不够?换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版,能一步步看着 循环轮转矩阵 的数据怎么变、指针怎么走,还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路是什么?+
把矩阵看成一圈套一圈的同心方环,对每一层单独处理。从左上角起顺时针把环上的值抄成一条一维的链,轮转 k 次等价于这条链循环左移 k 位,用取模把 k 压到不超过环长,再按原来的位置顺序把新链摆回环里。逐层做完就是答案。
为什么 k 要先取模,不取会怎样?+
k 的上界能到十的九次方,如果老实地一次挪一格转 k 遍,时间会爆炸。但一条链转满自己的长度就回到原位,所以 k 对环长取模后,余数才是真正需要挪的位数。取模把可能上亿次的操作压成常数级的一次搬运。
时间和空间复杂度各是多少?+
时间 O(m 乘 n),所有层的环加起来就是整个矩阵,每个格子只被读写常数次,k 靠取模不会真的转很多遍。空间 O(m 加 n),每次只为当前层开一条链,最外层那条最长,长度是 O(m 加 n),逐层复用不额外叠加。
想听吴师兄把这道题讲给你听?
文字版和动画都随便看。开通图解算法年卡,可以听吴师兄声线把 循环轮转矩阵 一步步讲透(全站 0 节语音精讲,持续扩充), 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构,与华为技术有限公司无任何关联;课程的服务内容与权益以购买协议为准,学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述,相关商标归各自权利人所有。