LeetCode 1260 Shift 2D Grid 全面解析四种解法从模拟到降维映射【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 1260「Shift 2D Grid」展开系统讲解二维网格整体右移一位的四种经典实现暴力模拟、原地旋转、降维三次反转与直接目标位置映射并配合本仓库 python/1260-shift-2d-grid.py、cpp/1260-shift-2d-grid.cpp、java/1260-shift-2d-grid.java 等多语言源码佐证。读者学完后将掌握 2D 坐标与 1D 线性索引互转、模运算处理环形回绕以及如何把 O(k·m·n) 的朴素解法优化到 O(m·n) 的单遍解法。1. 问题定义与前置知识题目本质给定一个m行n列的二维网格grid与一个整数k要求把整个网格中的元素整体向右侧移动k次。移动规则可概括为每个元素移动到同一行的下一列即(r, c) - (r, c 1)行末元素回绕到下一行开头即(r, n-1) - ((r 1) % m, 0)整个网格的最后一个元素(m-1, n-1)回绕到起点(0, 0)。换句话说shift 2d grid等价于把网格按行展开后做一维数组的循环右移k位只是移动发生在二维坐标上。需要掌握的四项前置能力在动手实现前建议先确认自己对以下概念足够熟悉它们也是本仓库大量矩阵类题目的通用基础二维数组/矩阵遍历用行、列下标(r, c)访问和修改元素。数组循环移位理解元素在环形序列中如何前移/后移例如 rotate-array、rotate-matrix 等题的核心思想。索引映射在 2D 坐标(r, c)与 1D 线性索引之间互相转换。标准公式为index r * n c反向为r index / n、c index % n。模运算用取模处理越界回绕例如(r 1) % m保证行号在[0, m-1]内循环。2. 解法一暴力模拟额外空间思路这是最直观的做法把「向右移动一格」这件事重复执行k次。每一次移动都基于当前网格生成一个新网格前n-1列元素右移一格最后一列元素通过模运算回绕到下一行开头。整个网格的移动方式与「所有元素在环形队列中前进一步」完全一致。算法步骤外层循环执行k次移位每次迭代创建一个全 0 的新网格cur将原网格第c列的元素复制到cur的第c 1列同一行内单独处理最后一列(r, n-1)处的元素回绕到cur[(r 1) % m][0]用cur替换原网格进入下一次移位返回最终的网格。多语言实现以 Python 为例其余语言逻辑完全一致class Solution: def shiftGrid(self, grid: List[List[int]], k: int) - List[List[int]]: m, n len(grid), len(grid[0]) while k: cur [[0] * n for _ in range(m)] for r in range(m): for c in range(n - 1): cur[r][c 1] grid[r][c] for r in range(m): cur[(r 1) % m][0] grid[r][n - 1] grid cur k - 1 return gridC 版本通过vectorvectorint cur(m, vectorint(n, 0))初始化新网格其余循环结构相同Java 版本在返回前还需把int[][]逐行转成ListListIntegerGo 版本使用make([][]int, m)后逐行make([]int, n)。各语言完整实现可对照本仓库对应题目文件查看。复杂度分析时间复杂度O(k · m · n)——每次移位都要遍历全部m × n个元素共执行k次空间复杂度O(m · n)——每轮迭代都需要一个全新的网格cur。其中m为行数n为列数k为移位次数。当k很大时例如k接近10^4量级该方案会超时因此需要后续更优解法。3. 解法二原地模拟swap 传播思路解法一每轮都要新建整个网格空间开销大。解法二尝试原地完成单次移位把移位看作一次循环接力——每个元素占据前一个元素的位置。只要预先保存最后一个元素grid[m-1][n-1]作为prev然后按行优先顺序遍历网格在遍历过程中不断把「当前元素」与prev交换就能让每个值自然地向后传递一格形成一次完整的循环右移。算法步骤外层循环执行k次保存最后一个元素grid[m-1][n-1]为prev按行、列顺序遍历每个格子将当前元素与prev交换swap(grid[r][c], prev)一轮遍历结束后整个网格等效于右移了一格返回网格。多语言实现class Solution: def shiftGrid(self, grid: List[List[int]], k: int) - List[List[int]]: m, n len(grid), len(grid[0]) while k: prev grid[m - 1][n - 1] for r in range(m): for c in range(n): grid[r][c], prev prev, grid[r][c] k - 1 return gridC 版本直接用标准库swap(grid[r][c], prev)Rust 由于所有权限制使用std::mem::swap(mut grid[r][c], mut prev)JavaScript 则借助数组解构[prev, grid[r][c]] [grid[r][c], prev]完成交换。复杂度分析时间复杂度O(k · m · n)——仍是k轮全量遍历空间复杂度O(1)不计输出结果——这是相比解法一的优势不再需要每轮分配新网格仅在原地做 swap 传播。注意对于返回ListListInteger的语言Java、C#、Kotlin最终仍需要把二维数组转换为对应的列表结构这部分额外空间不计入算法核心空间复杂度。4. 解法三降维成一维数组 三次反转思路既然「2D 网格右移」本质上等价于「按行展开的一维数组循环右移」那么可以先把网格拉平为一维数组套用经典的三次反转法完成循环右移再还原回二维网格。这也是 rotate-array 题目中数组轮转的通用套路。三次反转的原理要将数组循环右移k位先整体反转再反转前k个元素最后反转剩余元素。例如数组[1,2,3,4,5]右移 2 位整体反转 →[5,4,3,2,1]反转前 2 个 →[4,5,3,2,1]反转剩余 3 个 →[4,5,1,2,3]得到正确结果。算法步骤展平网格为一维数组arr映射关系为arr[r * n c] grid[r][c]对k取模k % NN m * n消除多余整圈旋转反转整个数组反转前k个元素反转从下标k到N-1的剩余元素把一维数组映射回二维网格返回结果。多语言实现class Solution: def shiftGrid(self, grid: List[List[int]], k: int) - List[List[int]]: m, n len(grid), len(grid[0]) N m * n k % N arr [0] * N for r in range(m): for c in range(n): arr[r * n c] grid[r][c] def reverse(l, r): while l r: arr[l], arr[r] arr[r], arr[l] l 1 r - 1 reverse(0, N - 1) reverse(0, k - 1) reverse(k, N - 1) for r in range(m): for c in range(n): grid[r][c] arr[r * n c] return gridC 版本更简洁reverse(arr.begin(), arr.end())、reverse(arr.begin(), arr.begin() k)、reverse(arr.begin() k, arr.end())三段式调用标准库即可Rust 则利用切片方法arr.reverse()、arr[..k].reverse()、arr[k..].reverse()。复杂度分析时间复杂度O(m · n)——三次反转各自是线性扫描展平与还原也是线性总共 O(m·n)与k无关空间复杂度O(m · n)——需要一维数组arr存放展平后的数据。5. 解法四直接计算目标位置单遍映射思路前面几种方案要么反复移动、要么借助额外数组做转换而解法四追求一步到位既然每个元素经过k次移位后的落点是唯一确定的那就直接算出每个元素的目标坐标一次遍历放置完毕。关键洞察元素在原网格中的一维下标为pos r * n c向右移动k位后的新一维下标为(pos k) % (m * n)取模保证环形回绕再通过newR newVal / n、newC newVal % n还原成二维坐标即可。算法步骤创建与输入同尺寸的结果网格遍历每个格子(r, c)计算新的一维下标newVal (r * n c k) % (m * n)换算回二维坐标newR newVal / nnewC newVal % n将原值放入res[newR][newC]返回结果网格。多语言实现class Solution: def shiftGrid(self, grid: List[List[int]], k: int) - List[List[int]]: M, N len(grid), len(grid[0]) def posToVal(r, c): return r * N c def valToPos(v): return [v // N, v % N] res [[0] * N for _ in range(M)] for r in range(M): for c in range(N): newVal (posToVal(r, c) k) % (M * N) newR, newC valToPos(newVal) res[newR][newC] grid[r][c] return res仓库源码印证本仓库中 5 种语言的题目实现均采用这一解法可直接对照阅读python/1260-shift-2d-grid.py用嵌套函数posToVal/valToPos封装坐标互转valToPos返回[v // N, v % N]即(r, c)cpp/1260-shift-2d-grid.cpp用 lambda 表达式auto posToVal - int与valToPos完成同样的映射java/1260-shift-2d-grid.java使用BiFunctionInteger, Integer, Integer与FunctionInteger, int[]实现坐标互转并通过res.get(newRC[ROW]).set(newRC[COL], grid[r][c])原地写入结果列表javascript/1260-shift-2d-grid.jsvalToPos (v) [Math.floor(v / N), v % N]注意 JS 除法需显式Math.floor取整kotlin/1260-shift-2d-grid.kt用(v / n) to (v % n)返回 Pair 解构为(newR, newC)。从源码结构可以看出该解法把「二维坐标 ↔ 一维下标」的双向映射抽象成独立函数是四种方案中结构最清晰、最容易向任意维度推广的写法。复杂度分析时间复杂度O(m · n)——每个元素恰好处理一次与k的大小无关空间复杂度O(m · n)——需要一个与输入等大的结果网格。6. 常见错误与排查错误一没有对 k 取模当k大于元素总数m * n时完整旋转m * n次后网格会回到初始状态继续暴力执行k次移位属于大量冗余计算可能导致超时TLE。正确做法是先把k规约为k % (m * n)。这一点在解法三、解法四中天然满足解法四的取模运算内置于位置计算公式而解法一、解法二如果直接循环k次则必须提前取模。错误二2D 与 1D 索引互转公式写错展平网格或计算新位置时若 2D 坐标与 1D 索引的换算关系写错元素会被放到错误的位置且这类错误很难通过肉眼排查。必须牢记并统一使用正向index r * n c反向r index / nc index % n特别提醒反向换算中的除数一定是列数n而不是行数m——这是最容易写错的地方。错误三忽略行末元素的回绕在解法一的逐列复制中最后一列(r, n-1)不能简单地复制到(r, n)越界而必须通过((r 1) % m, 0)回绕到下一行首列同理最后一行的末元素应回到(0, 0)。忘记模运算会直接导致数组越界或结果错乱。7. 四种解法对比与选型建议解法核心思想时间复杂度空间复杂度适用场景解法一模拟额外空间逐轮复制到新网格O(k·m·n)O(m·n)仅当k很小时直观可写解法二原地模拟swap 循环传播O(k·m·n)O(1)想省空间但k仍需很小解法三降维 三次反转展平后套用数组轮转O(m·n)O(m·n)熟悉数组反转套路代码短解法四直接目标位置映射一维下标 k 取模一步定位O(m·n)O(m·n)面试/竞赛首选思路清晰无副作用选型建议本仓库各语言的 1260 题实现 统一选择了解法四——它既规避了k过大导致的超时风险又不需要额外的反转逻辑与坐标往返代码可读性最好是实际面试中最推荐的方案。8. 延伸思考本题的「2D 坐标 ↔ 1D 下标 模运算」模式在本仓库的矩阵类题目中反复出现例如 rotate-matrix矩阵旋转、rotate-array一维数组轮转都依赖相同的坐标映射与取模回绕思想。掌握本题后你可以进一步思考如果移位方向改为「向左」「向上」「向下」坐标公式该如何对称调整如果网格不是矩形而是锯齿状每行长度不同展平公式又该如何推广这些都是面试官常用的变体追问。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
