解题思路

题目的条件很友好地指明 m 和 n 均为偶数，那么我们易得：在一个 $m \times n$ 的矩阵中，总共有 $\min(m, n) / 2$ 圈。我们可设最外层为第 $0$ 圈，那么我们易得该圈的元素个数 sz 为 $2(m+n)-4$，根据数学归纳法，我们可知第 $i$ 圈的元素个数 sz 为 $2(m+n-4i) - 4$。因此我们对第 $i$ 圈进行旋转 $k$ 次时，实际上相当于我们对该圈旋转了 k % sz 次。

现在我们需要推出第 $i$ 圈元素的坐标，同理，我们可从第 $0$ 圈获得启发。易知第 $0$ 圈的元素坐标从左上角顺时针依次为 $(0, 0), (0,1), \cdots, (0, n-1), (1, n-1), \cdots, (m-1, n-1), \cdots, (m-1, 1), (m-1, 0), \cdots, (1, 0)$。我们可推出第 $i$ 圈的元素坐标从左上角顺时针依次为 $(i, i), \cdots, (i, n-i-1), \cdots, (m-i-1, n-i-1), \cdots, (m-i-1, i), \cdots, (i+1, i)$。

对于第 $i$ 圈上的点坐标 $(x, y)$，我们可分为四个边：

• $x = i,\ y < n-i-1$，与其右侧交换
• $x < m-i-1,\ y = n-i-1$，与其下侧交换
• $x = m-i-1,\ y > i$，与其左侧交换
• $x > i,\ y = i$，与其上侧交换

每次旋转我们需要完成 sz - 1次交换。

代码

###C++

class Solution {
private:
    int m, n, layer;
    
    void rotateLayer(vector<vector<int>>& grid, int i, int k) {
        int sz = 2 * (m + n - 4*i) - 4;
        k %= sz;
        
        while (k--) {
            int x = i, y = i;
            for (int j = 0; j < sz-1; ++j) {
                if (x == i && y < n-i-1) {
                    swap(grid[x][y], grid[x][y+1]);
                    ++y;
                } else if (x < m-i-1 && y == n-i-1) {
                    swap(grid[x][y], grid[x+1][y]);
                    ++x;
                } else if (x == m-i-1 && y > i) {
                    swap(grid[x][y], grid[x][y-1]);
                    --y;
                } else if (x > i && y == i) {
                    swap(grid[x][y], grid[x-1][y]);
                    --x;
                }
            }
        }
    }
    
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        m = grid.size(), n = grid[0].size();
        layer = min(m, n) / 2;
        
        for (int i = 0; i < layer; ++i) {
            rotateLayer(grid, i, k);
        }
        
        return grid;
    }
};

###Golang

func rotateGrid(grid [][]int, k int) [][]int {
    m, n := len(grid), len(grid[0])
    layer := m / 2
    if n < m {
        layer = n / 2
    }
    
    rotateLayer := func(i int) {
        sz := 2 * (m + n - 4*i) - 4
        kk := k % sz
        
        for kk > 0 {
            x, y := i, i
            for j := 0; j < sz-1; j++ {
                if x == i && y < n-i-1 {
                    grid[x][y], grid[x][y+1] = grid[x][y+1], grid[x][y]
                    y++
                } else if x < m-i-1 && y == n-i-1 {
                    grid[x][y], grid[x+1][y] = grid[x+1][y], grid[x][y]
                    x++
                } else if x == m-i-1 && y > i {
                    grid[x][y], grid[x][y-1] = grid[x][y-1], grid[x][y]
                    y--
                } else if x > i && y == i {
                    grid[x][y], grid[x-1][y] = grid[x-1][y], grid[x][y]
                    x--
                }
            }
            kk--
        }
    }
    
    for i := 0; i < layer; i++ {
        rotateLayer(i)
    }
    
    return grid
}