LeetCode 1260. 二维网格迁移
题目描述
有一个 \(m \times n\) 的二维整数网格 grid 和一个整数 \(k\)，需要将网格中的元素按顺序迁移 \(k\) 次。
迁移规则：
- 网格中的每个元素会移动到它的“下一个”位置。
- “下一个”位置的定义是：如果我们将网格展开为一个一维数组（按行主序，即第一行 → 第二行 → ... → 最后一行），那么每个元素会移动到数组中它后面的一个位置。
- 最后一个元素会移动到第一个位置。
换句话说，迁移一次相当于：
- 将
grid按行主序展开成一个一维数组arr，长度为 \(m \times n\)。 - 将
arr整体循环右移一位（最后一个元素移到开头）。 - 再将
arr按行主序填回 \(m \times n\) 的网格。
要求：返回迁移 \(k\) 次后的网格。
示例
假设网格为：
\[\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \]
展开为一维数组：
\[[1, 2, 3, 4, 5, 6, 7, 8, 9] \]
迁移一次后（循环右移一位）：
\[[9, 1, 2, 3, 4, 5, 6, 7, 8] \]
再按 3×3 网格排列：
\[\begin{bmatrix} 9 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{bmatrix} \]
解题思路
步骤 1：理解映射关系
假设网格中位置 \((i, j)\) 在原网格中对应的一维索引是：
\[\text{index} = i \times n + j \]
其中 \(n\) 是列数，\(0 \le i < m, 0 \le j < n\)。
迁移 \(k\) 次后，这个位置的新值应该来自原网格中某个位置 \((r, c)\)，这个位置的一维索引满足：
新索引 = 原索引 - k（在模运算下），因为循环右移 k 位相当于原数组左移 k 位到新位置。更准确地说：
新网格的一维索引 \(p\) 处的值 = 原网格一维索引 \(q\) 处的值，其中
\[q = (p - k) \bmod (m \times n) \]
但为了避免负数，可以写成：
\[q = (p - k + m \times n) \bmod (m \times n) \]
其中 \(p = i \times n + j\)。
步骤 2：简化思路
我们不需要展开数组再重组，可以直接计算每个新位置的值来自原网格的哪个位置。
设总元素数 \(N = m \times n\)。
新网格的 (i, j) 对应一维索引：
\[p = i \times n + j \]
它对应的原网格一维索引：
\[q = (p - k) \bmod N \]
原网格位置：
\[r = q / n,\quad c = q \% n \]
所以：
\[\text{newGrid}[i][j] = \text{grid}[r][c] \]
步骤 3：举例验证
网格 2×2：
\[\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \]
k=1，N=4。
新网格(0,0): p=0, q=(0-1+4)%4=3, 原位置(3/2=1, 3%2=1) → grid[1][1]=4。
新网格(0,1): p=1, q=0, 原位置(0,0) → 1。
新网格(1,0): p=2, q=1, 原位置(0,1) → 2。
新网格(1,1): p=3, q=2, 原位置(1,0) → 3。
结果：
\[\begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} \]
正确。
步骤 4：优化 k 值
迁移 N 次等于恢复原状，所以实际上只需要迁移 \(k \bmod N\) 次。设 \(k = k \bmod N\)。
如果 k=0，直接返回原网格。
步骤 5：实现步骤
- 计算 m, n, 以及 N = m*n, k = k % N。
- 初始化一个 m 行 n 列的结果数组。
- 遍历新网格的每个位置 (i, j)：
- 计算 p = i * n + j
- 计算 q = (p - k + N) % N
- 计算原位置 r = q / n, c = q % n
- 结果[i][j] = grid[r][c]
- 返回结果。
时间复杂度：O(mn)，空间复杂度：O(mn) 用于存储新网格。
示例推导（完整过程）
输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k=1
m=3, n=3, N=9, k=1%9=1。
遍历新网格：
- i=0,j=0 → p=0 → q=(0-1+9)%9=8 → r=8/3=2, c=8%3=2 → grid[2][2]=9 → 新[0][0]=9
- i=0,j=1 → p=1 → q=0 → r=0,c=0 → 1 → 新[0][1]=1
- i=0,j=2 → p=2 → q=1 → r=0,c=1 → 2 → 新[0][2]=2
- i=1,j=0 → p=3 → q=2 → r=0,c=2 → 3 → 新[1][0]=3
- i=1,j=1 → p=4 → q=3 → r=1,c=0 → 4 → 新[1][1]=4
- i=1,j=2 → p=5 → q=4 → r=1,c=1 → 5 → 新[1][2]=5
- i=2,j=0 → p=6 → q=5 → r=1,c=2 → 6 → 新[2][0]=6
- i=2,j=1 → p=7 → q=6 → r=2,c=0 → 7 → 新[2][1]=7
- i=2,j=2 → p=8 → q=7 → r=2,c=1 → 8 → 新[2][2]=8
结果：
[[9,1,2],[3,4,5],[6,7,8]]，与示例一致。