用 K 元素逆时针旋转矩阵的每个环 · GeeksForGeeks 中文系列教程

# 用 K 元素逆时针旋转矩阵的每个环 > 原文： [https://www.geeksforgeeks.org/rotate-ring-matrix-anticlockwise-k-elements/](https://www.geeksforgeeks.org/rotate-ring-matrix-anticlockwise-k-elements/) 给定一个阶数为 M * N 且值为 K 的矩阵，任务是将矩阵的每个环逆时针旋转 K 个元素。如果任何一个环中的元素都小于等于 K，则不要旋转它。例子： ``` Input : k = 3 mat[4][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}} Output: 4 8 12 16 3 10 6 15 2 11 7 14 1 5 9 13 Input : k = 2 mat[3][4] = {{1, 2, 3, 4}, {10, 11, 12, 5}, {9, 8, 7, 6}} Output: 3 4 5 6 2 11 12 7 1 10 9 8 ``` 这个想法是遍历[螺旋](https://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/)形式的矩阵。这是解决此问题的算法： * 制作一个大小为 M * N 的辅助数组 **temp []** 。 * 开始以螺旋形式遍历矩阵并将当前环的元素存储在 temp []数组中。在临时存储元素时，请跟踪当前环的开始和结束位置。 * 对于存储在 temp []中的每个环，[旋转](https://www.geeksforgeeks.org/program-for-array-rotation-continued-reversal-algorithm)该子数组 temp [] * 对矩阵的每个环重复此过程。 * 在最后一个遍历矩阵中，再次螺旋旋转并将 temp []数组的元素复制到矩阵。以下是上述步骤的 C++ 实现。 ``` // C++ program to rotate individual rings by k in // spiral order traversal. #include<bits/stdc++.h> #define MAX 100 using namespace std; // Fills temp array into mat[][] using spiral order // traveral. void fillSpiral(int mat[][MAX], int m, int n, int temp[]) { int i, k = 0, l = 0; /* k - starting row index m - ending row index l - starting column index n - ending column index */ int tIdx = 0; // Index in temp array while (k < m && l < n) { /* first row from the remaining rows */ for (int i = l; i < n; ++i) mat[k][i] = temp[tIdx++]; k++; /* last column from the remaining columns */ for (int i = k; i < m; ++i) mat[i][n-1] = temp[tIdx++]; n--; /* last row from the remaining rows */ if (k < m) { for (int i = n-1; i >= l; --i) mat[m-1][i] = temp[tIdx++]; m--; } /* first column from the remaining columns */ if (l < n) { for (int i = m-1; i >= k; --i) mat[i][l] = temp[tIdx++]; l++; } } } // Function to spirally traverse matrix and // rotate each ring of matrix by K elements // mat[][] --> matrix of elements // M --> number of rows // N --> number of columns void spiralRotate(int mat[][MAX], int M, int N, int k) { // Create a temporary array to store the result int temp[M*N]; /* s - starting row index m - ending row index l - starting column index n - ending column index; */ int m = M, n = N, s = 0, l = 0; int *start = temp; // Start position of current ring int tIdx = 0; // Index in temp while (s < m && l < n) { // Initialize end position of current ring int *end = start; // copy the first row from the remaining rows for (int i = l; i < n; ++i) { temp[tIdx++] = mat[s][i]; end++; } s++; // copy the last column from the remaining columns for (int i = s; i < m; ++i) { temp[tIdx++] = mat[i][n-1]; end++; } n--; // copy the last row from the remaining rows if (s < m) { for (int i = n-1; i >= l; --i) { temp[tIdx++] = mat[m-1][i]; end++; } m--; } /* copy the first column from the remaining columns */ if (l < n) { for (int i = m-1; i >= s; --i) { temp[tIdx++] = mat[i][l]; end++; } l++; } // if elements in current ring greater than // k then rotate elements of current ring if (end-start > k) { // Rotate current ring using revarsal // algorithm for rotation reverse(start, start+k); reverse(start+k, end); reverse(start, end); // Reset start for next ring start = end; } else // There are less than k elements in ring break; } // Fill tenp array in original matrix. fillSpiral(mat, M, N, temp); } // Driver program to run the case int main() { // Your C++ Code int M = 4, N = 4, k = 3; int mat[][MAX]= {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16} }; spiralRotate(mat, M, N, k); // print modified matrix for (int i=0; i<M; i++) { for (int j=0; j<N; j++) cout << mat[i][j] << " "; cout << endl; } return 0; } ``` 输出： ``` 4 8 12 16 3 10 6 15 2 11 7 14 1 5 9 13 ``` 时间复杂度：O（M * N）辅助空间：O（M * N）本文由 [**Shashank Mishra（Gullu）**](https://www.facebook.com/shashank.mishra.92167) 贡献。如果您喜欢 GeeksforGeeks 并希望做出贡献，则还可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。