java 解法, 执行用时: 4 ms, 内存消耗: 43.3 MB, 提交时间: 2023-09-25 15:58:07

class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        // 矩阵尺寸
        int m = grid.length, n = grid[0].length;
        // 计算一共有多少层
        int layerNumber = Math.min(m, n) / 2;
        // 逐层处理
        for (int i = 0; i < layerNumber; ++i) {
            // 计算出来当前层需要多大的数组来存放, 计算方法是当前层最大尺寸 - 内部下一层尺寸.
            int[] data = new int[(m - 2 * i) * (n - 2 * i) - (m - (i + 1) * 2) * (n - (i + 1) * 2)];
            int idx = 0;
            // 从左往右
            for (int offset = i; offset < n - i - 1; ++offset)
                data[idx++] = grid[i][offset];
            // 从上往下
            for (int offset = i; offset < m - i - 1; ++offset)
                data[idx++] = grid[offset][n - i - 1];
            // 从右往左
            for (int offset = n - i - 1; offset > i; --offset)
                data[idx++] = grid[m - i - 1][offset];
            // 从下往上
            for (int offset = m - i - 1; offset > i; --offset)
                data[idx++] = grid[offset][i];
            // 把旋转完的放回去
            Integer[] ret = rotateVector(data, k);
            idx = 0;
            // 从左往右
            for (int offset = i; offset < n - i - 1; ++offset)
                grid[i][offset] = ret[idx++];
            // 从上往下
            for (int offset = i; offset < m - i - 1; ++offset)
                grid[offset][n - i - 1] = ret[idx++];
            // 从右往左
            for (int offset = n - i - 1; offset > i; --offset)
                grid[m - i - 1][offset] = ret[idx++];
            // 从下往上
            for (int offset = m - i - 1; offset > i; --offset)
                grid[offset][i] = ret[idx++];
        }
        return grid;
    }

    private Integer[] rotateVector(int[] vector, int offset) {
        // 取余, 否则会有无用功, 超时
        offset = offset % vector.length;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int item : vector) deque.add(item);
        // 旋转操作
        while (offset-- > 0) {
            deque.addLast(deque.pollFirst());
        }
        return deque.toArray(new Integer[0]);
    }
}

python3 解法, 执行用时: 144 ms, 内存消耗: 16.4 MB, 提交时间: 2023-09-25 15:57:41

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        nlayer = min(m // 2, n // 2)   # 层数
        # 从左上角起逆时针枚举每一层
        for layer in range(nlayer):
            r = []   # 每个元素的行下标
            c = []   # 每个元素的列下标
            val = []   # 每个元素的数值
            for i in range(layer, m - layer - 1):   # 左 
                r.append(i)
                c.append(layer)
                val.append(grid[i][layer])
            for j in range(layer, n - layer - 1):   # 下
                r.append(m - layer - 1)
                c.append(j)
                val.append(grid[m-layer-1][j])
            for i in range(m - layer - 1, layer, -1):   # 右
                r.append(i)
                c.append(n - layer - 1)
                val.append(grid[i][n-layer-1])
            for j in range(n - layer - 1, layer, -1):   # 上
                r.append(layer)
                c.append(j)
                val.append(grid[layer][j])
            total = len(val)   # 每一层的元素总数
            kk = k % total   # 等效轮转次数
            # 找到每个下标对应的轮转后的取值
            for i in range(total):
                idx = (i + total - kk) % total   # 轮转后取值对应的下标
                grid[r[i]][c[i]] = val[idx]
        return grid

cpp 解法, 执行用时: 28 ms, 内存消耗: 16 MB, 提交时间: 2023-09-25 15:57:14

// 枚举每一层
class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int nlayer = min(m / 2, n / 2);   // 层数
        // 从左上角起逆时针枚举每一层
        for (int layer = 0; layer < nlayer; ++layer){
            vector<int> r, c, val;   // 每个元素的行下标，列下标与数值
            for (int i = layer; i < m - layer - 1; ++i){   // 左
                r.push_back(i);
                c.push_back(layer);
                val.push_back(grid[i][layer]);
            }
            for (int j = layer; j < n - layer - 1; ++j){   // 下
                r.push_back(m - layer - 1);
                c.push_back(j);
                val.push_back(grid[m-layer-1][j]);
            }
            for (int i = m - layer - 1; i > layer; --i){   // 右
                r.push_back(i);
                c.push_back(n - layer - 1);
                val.push_back(grid[i][n-layer-1]);
            }
            for (int j = n - layer - 1; j > layer; --j){   // 上
                r.push_back(layer);
                c.push_back(j);
                val.push_back(grid[layer][j]);
            }
            int total = val.size();   // 每一层的元素总数
            int kk = k % total;   // 等效轮转次数
            // 找到每个下标对应的轮转后的取值
            for (int i = 0; i < total; ++i){
                int idx = (i + total - kk) % total;   // 轮转后取值对应的下标
                grid[r[i]][c[i]] = val[idx];
            }
        }
        return grid;
    }
};

golang 解法, 执行用时: 20 ms, 内存消耗: 7 MB, 提交时间: 2023-09-25 15:56:41

func rotateGrid(a [][]int, k int) [][]int {
	n, m := len(a), len(a[0])
	ans := make([][]int, n)
	for i := range ans {
		ans[i] = make([]int, m)
	}
	lim := min(n, m) / 2
	for d := 0; d < lim; d++ {
		b := make([]int, 0, (n+m-d*4-2)*2)
		for j := d; j < m-d; j++ { // →
			b = append(b, a[d][j])
		}
		for i := d + 1; i < n-d; i++ { // ↓
			b = append(b, a[i][m-1-d])
		}
		for j := m - d - 2; j >= d; j-- { // ←
			b = append(b, a[n-1-d][j])
		}
		for i := n - d - 2; i > d; i-- { // ↑
			b = append(b, a[i][d])
		}
		shift := k % len(b)
		b = append(b[shift:], b[:shift]...) // 旋转数组
		j := 0
		for i := d; i < m-d; i++ { // →
			ans[d][i] = b[j]
			j++
		}
		for i := d + 1; i < n-d; i++ { // ↓
			ans[i][m-1-d] = b[j]
			j++
		}
		for i := m - d - 2; i >= d; i-- { // ←
			ans[n-1-d][i] = b[j]
			j++
		}
		for i := n - d - 2; i > d; i-- { // ↑
			ans[i][d] = b[j]
			j++
		}
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}