题目描述

给你一个 m 行 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 次迁移操作后最终得到的 二维网格。
  

输入与输出

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

提示

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

思路

将二维展开成一维，其实就是将一维数组向后移动k，然后再拼接成二维。

AC代码

class Solution {
    
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
    
        int n = grid.size();
        int m = grid[0].size();
        vector<int> temp;
        for (int i = 0; i < n; ++i) {
    
            for (int j = 0; j < m; ++j) {
    
                temp.push_back(grid[i][j]);
            }
        }
        int len = n * m;
        int t = k;
        int pos = 0;
        t %= len;
        for (int i = 0; i < n; ++i) {
    
            for (int j = 0; j < m; ++j) {
    
                if (t > 0) {
    
                    grid[i][j] = temp[len - t];
                    t--;
                } else {
    
                    grid[i][j] = temp[pos];
                    pos++;
                }
            }
        }
        return grid;
    }
};

时间复杂度和空间复杂度都为O(m*n)