Go语言解决LeetCode 1260：二维网格迁移算法解析

巷口听风

发布时间：2026-10-15 | 4人浏览过

原创

LeetCode 1260题要求将m*n的二维网格进行k次循环迁移。核心难点在于高效模拟k次移动而不产生大量重复计算。通过将二维坐标映射为一维数组，利用取模运算确定有效步数，并根据k值与总长度一半的关系选择向左或向右平移，可一次性完成所有元素的重新排列，显著降低时间复杂度。

题目核心逻辑

题目给出的迁移规则定义了元素在网格中的流动路径：grid[i][j] 移至 grid[i][j+1]；当到达行尾时，移至下一行首 grid[i+1][0]；若到达右下角 grid[m-1][n-1]，则回到左上角 grid[0][0]。
这种连续不断的线性位移可以看作是一个环形队列的旋转。若直接将此过程模拟为k次独立的矩阵遍历，在k较大时效率极低。

第1步：理解数据映射关系

观察迁移路径可知，整个二维网格实际上是一个被展开的一维线性序列。对于任意元素 grid[i][j]，它在展开后的一维数组中的索引为 i * n + j。
因此，问题转化为：在一个长度为 m * n 的一维数组中，将其元素整体向右循环移动 k 位，最后再还原回二维结构。

以示例1为例，输入 grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1。
展开为一维：[1,2,3,4,5,6,7,8,9]。
向右移动1位后变为：[9,1,2,3,4,5,6,7,8]。
再还原为二维即为输出结果。

算法优化思路

直接模拟每次迁移不仅速度慢，还容易出错。我们可以采用“一次到位”的策略，但需处理两个关键优化点：

取模简化步数：网格总长度为 L = m * n。移动 L 次等同于原位置不动。因此，实际有效移动步数为 k % L。
左右移动方向选择：当 k % L 较大时（超过总长的一半），向右循环移动的效率低于向左移动。例如总长9，k=8。向右移8步等价于向左移1步。比较 k_remainder 与 L/2，若前者大，则转换为向左移动 L - k_remainder 步，通常能减少部分内存拷贝操作的复杂性。

Go语言代码实现

以下实现采用了空间换时间的策略：先展平数组，调整后再重塑。虽然使用了额外的一维临时数组（长度与原网格相同），但避免了频繁创建切片或多次遍历矩阵。

func shiftGrid(grid [][]int, k int) [][]int {
    m := len(grid)
    n := len(grid[0])
    total := m * n
    
    // 1. 提取扁平化数组
    flat := make([]int, total)
    idx := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            flat[idx] = grid[i][j]
            idx++
        }
    }
    
    // 2. 处理有效步数
    step := k % total
    if step == 0 {
        return grid // 不需要移动
    }
    
    // 3. 决定移动方向以减少操作量
    res := make([]int, total)
    if step < total/2 {
        // 向右移 step 位：尾部取 step 个放到最前面
        // 后半段 (total-step ~ total-1) -> 前部 (0 ~ step-1)
        copy(res[:step], flat[total-step:])
        // 前半段 (0 ~ total-step-1) -> 后部 (step ~ total-1)
        copy(res[step:], flat[:total-step])
    } else {
        // 相当于向左移 total-step 位：头部取 step 个放到最后面
        leftStep := total - step
        // 前半段 (0 ~ leftStep-1) -> 尾部 (step ~ total-1)
        copy(res[step:], flat[:leftStep])
        // 后半段 (leftStep ~ total-1) -> 前部 (0 ~ step-1)
        copy(res[:step], flat[leftStep:])
    }
    
    // 4. 重塑为二维网格
    result := make([][]int, m)
    for i := 0; i < m; i++ {
        result[i] = make([]int, n)
        for j := 0; j < n; j++ {
            result[i][j] = res[i*n+j]
        }
    }
    
    return result
}