Easy

题目描述

给你一个 m x n 的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。

每次迁移操作将会引发下述活动：

  • 位于 grid[i][j] 的元素将会移动到 grid[i][j + 1]。
  • 位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
  • 位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。

请你返回 k 次迁移操作后最终得到的二维网格。

示例 1：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[9,1,2],[3,4,5],[6,7,8]]

示例 2：

输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

示例 3：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
输出：[[1,2,3],[4,5,6],[7,8,9]]

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m <= 50
  • 1 <= n <= 50
  • -1000 <= grid[i][j] <= 1000
  • 0 <= k <= 100

解题思路

这道题有两种主要思路：

思路一：模拟迁移过程 我们可以按照题目描述，逐步进行 k 次迁移操作。每次迁移时，我们从后往前遍历网格，将每个元素移动到下一个位置。这种方法直观但效率较低。

思路二：一维数组转换（推荐） 我们可以将二维网格看作一个一维数组，按行优先顺序排列。迁移 k 次相当于将数组向右循环移动 k 个位置。具体步骤：

  1. 将二维网格按行展开成一维数组
  2. 计算有效迁移次数：k % (m * n)，避免不必要的完整循环
  3. 将数组的后 k 个元素移到前面
  4. 将结果重新排列成二维网格

这种方法时间复杂度更优，且代码更简洁。由于网格大小最大为 50x50，空间开销也是可接受的。

关键优化：由于迁移具有周期性（每 m*n 次迁移后网格回到原状态），我们使用取模运算来减少实际操作次数。

代码实现

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        int total = m * n;
        k = k % total;
        
        // 将二维网格转换为一维数组
        vector<int> arr;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr.push_back(grid[i][j]);
            }
        }
        
        // 创建结果数组
        vector<int> shifted(total);
        for (int i = 0; i < total; i++) {
            shifted[(i + k) % total] = arr[i];
        }
        
        // 转换回二维网格
        vector<vector<int>> result(m, vector<int>(n));
        for (int i = 0; i < total; i++) {
            result[i / n][i % n] = shifted[i];
        }
        
        return result;
    }
};

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        total = m * n
        k = k % total
        
        # 将二维网格转换为一维数组
        arr = []
        for i in range(m):
            for j in range(n):
                arr.append(grid[i][j])
        
        # 执行迁移操作
        shifted = [0] * total
        for i in range(total):
            shifted[(i + k) % total] = arr[i]
        
        # 转换回二维网格
        result = [[0] * n for _ in range(m)]
        for i in range(total):
            result[i // n][i % n] = shifted[i]
        
        return result

public class Solution {
    public IList<IList<int>> ShiftGrid(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        int total = m * n;
        k = k % total;
        
        // 将二维网格转换为一维数组
        int[] arr = new int[total];
        int idx = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[idx++] = grid[i][j];
            }
        }
        
        // 执行迁移操作
        int[] shifted = new int[total];
        for (int i = 0; i < total; i++) {
            shifted[(i + k) % total] = arr[i];
        }
        
        // 转换回二维网格
        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < m; i++) {
            IList<int> row = new List<int>();
            for (int j = 0; j < n; j++) {
                row.Add(shifted[i * n + j]);
            }
            result.Add(row);
        }
        
        return result;
    }
}

var shiftGrid = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    const total = m * n;
    k = k % total;
    
    // 将二维网格转换为一维数组
    const arr = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            arr.push(grid[i][j]);
        }
    }
    
    // 执行迁移操作
    const shifted = new Array(total);
    for (let i = 0; i < total; i++) {
        shifted[(i + k) % total] = arr[i];
    }
    
    // 转换回二维网格
    const result = [];
    for (let i = 0; i < m; i++) {
        const row = [];
        for (let j = 0; j < n; j++) {
            row.push(shifted[i * n + j]);
        }
        result.push(row);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历整个网格三次：转换为一维、迁移操作、转换回二维
空间复杂度O(m × n)需要额外的一维数组存储元素，以及结果数组