用 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。