跳转至

1260.Shift 2D Grid

Tags: Easy Array

Links: https://leetcode.com/problems/shift-2d-grid/

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

  • Element at grid[i][j] moves to grid[i][j + 1].
  • Element at grid[i][n - 1] moves to grid[i + 1][0].
  • Element at grid[m - 1][n - 1] moves to grid[0][0].

Return the 2D grid after applying shift operation k times.

Example 1:

img

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Example 2:

img

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

Constraints:

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

数组旋转模型在二维的应用。

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = grid.size(), n =grid[0].size();
        while (k >= m * n) k -= m * n;
        k = m * n - k;
        if (k == 0) return grid;

        int step = GCD(k, m * n);
        for (int i = 0; i < step; ++i) {
            int pos = i;
            int x = i / n, y = i % n;
            int val = grid[x][y];

            while (true) {
                int j = pos + k;
                if (j >= m * n) j -= m * n;
                if (j == i) break;
                int row = j / n, col = j % n;
                grid[x][y] = grid[row][col];
                x = row; y = col;
                pos = j;
            }
            grid[x][y] = val;
        }

        return grid;
    }

    int GCD(int a, int b)
    {
        return b == 0 ? a : GCD(b, a % b);
    }
};