以矩阵的螺旋形式打印第 K 个元素 · GeeksForGeeks 中文系列教程

# 以矩阵的螺旋形式打印第 K 个元素 > 原文： [https://www.geeksforgeeks.org/print-kth-element-spiral-form-matrix/](https://www.geeksforgeeks.org/print-kth-element-spiral-form-matrix/) 给定 n X m 阶的 2D 矩阵，以矩阵的螺旋形式打印第 K 个元素。请参阅以下示例。 **示例**： ``` Input: mat[][] = {{1, 2, 3, 4} {5, 6, 7, 8} {9, 10, 11, 12} {13, 14, 15, 16}} k = 6 Output: 12 Explanation: The elements in spiral order is 1, 2, 3, 4, 8, 12, 16, 15... so the 6th element is 12 Input: mat[][] = {{1, 2, 3, 4, 5, 6} {7, 8, 9, 10, 11, 12} {13, 14, 15, 16, 17, 18}} k = 17 Output: 10 Explanation: The elements in spiral order is 1, 2, 3, 4, 5, 6, 12, 18, 17, 16, 15, 14, 13, 7, 8, 9, 10, 11 so the 17 th element is 10\. ``` **简单方法：** 一种简单的解决方案是开始以螺旋形式遍历矩阵[打印螺旋矩阵](https://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/)并启动计数器，即 count =0。只要 count 等于 K，就打印该元素。 * **算法**： 1. 保持变量 *count = 0* 以存储计数。 2. 从头到尾遍历矩阵。 3. 每次迭代将计数增加 1。 4. 如果计数等于 k 的给定值，则打印该元素并中断。 * **实现** ## C++ ``` #include <bits/stdc++.h> using namespace std; #define R 3 #define C 6 void spiralPrint(int m, int n, int a[R][C], int c) { int i, k = 0, l = 0; int count = 0; /* k - starting row index m - ending row index l - starting column index n - ending column index i - iterator */ while (k < m && l < n) { /* check the first row from the remaining rows */ for (i = l; i < n; ++i) { count++; if (count == c) cout << a[k][i] << " "; } k++; /* check the last column from the remaining columns */ for (i = k; i < m; ++i) { count++; if (count == c) cout << a[i][n - 1] << " "; } n--; /* check the last row from the remaining rows */ if (k < m) { for (i = n - 1; i >= l; --i) { count++; if (count == c) cout << a[m - 1][i] << " "; } m--; } /* check the first column from the remaining columns */ if (l < n) { for (i = m - 1; i >= k; --i) { count++; if (count == c) cout << a[i][l] << " "; } l++; } } } /* Driver program to test above functions */ int main() { int a[R][C] = { { 1, 2, 3, 4, 5, 6 }, { 7, 8, 9, 10, 11, 12 }, { 13, 14, 15, 16, 17, 18 } }, k = 17; spiralPrint(R, C, a, k); return 0; } ``` ## Java ``` import java.io.*; class GFG { static int R = 3; static int C = 6; static void spiralPrint(int m, int n, int[][] a, int c) { int i, k = 0, l = 0; int count = 0; /* k - starting row index m - ending row index l - starting column index n - ending column index i - iterator */ while (k < m && l < n) { /* check the first row from the remaining rows */ for (i = l; i < n; ++i) { count++; if (count == c) System.out.println(a[k][i]+" "); } k++; /* check the last column from the remaining columns */ for (i = k; i < m; ++i) { count++; if (count == c) System.out.println(a[i][n - 1]+" "); } n--; /* check the last row from the remaining rows */ if (k < m) { for (i = n - 1; i >= l; --i) { count++; if (count == c) System.out.println(a[m - 1][i]+" "); } m--; } /* check the first column from the remaining columns */ if (l < n) { for (i = m - 1; i >= k; --i) { count++; if (count == c) System.out.println(a[i][l]+" "); } l++; } } } /* Driver program to test above functions */ public static void main (String[] args) { int a[][] = { { 1, 2, 3, 4, 5, 6 }, { 7, 8, 9, 10, 11, 12 }, { 13, 14, 15, 16, 17, 18 } }; int k = 17; spiralPrint(R, C, a, k); } } // This code is contributed by shivanisinghss2110 ``` ## Python3 ``` R = 3 C = 6 def spiralPrint(m, n, a, c): k = 0 l = 0 count = 0 """ k - starting row index m - ending row index l - starting column index n - ending column index i - iterator """ while (k < m and l < n): for i in range(l,n): count+=1 if (count == c): print(a[k][i] , end=" ") k+=1 """ check the last column from the remaining columns """ for i in range(k,m): count+=1 if (count == c): print(a[i][n - 1],end=" ") n-=1 """ check the last row from the remaining rows """ if (k < m): for i in range(n - 1,l-1,-1): count+=1 if (count == c): print(a[m - 1][i],end=" ") m-=1 """ check the first column from the remaining columns """ if (l < n): for i in range(m - 1,k-1,-1): count+=1 if (count == c): print(a[i][l],end=" ") l+=1 """ Driver program to test above functions """ a = [[1, 2, 3, 4, 5, 6 ],[ 7, 8, 9, 10, 11, 12 ],[ 13, 14, 15, 16, 17, 18]] k = 17 spiralPrint(R, C, a, k) # This code is contributed by shivanisingh ``` **输出**： ``` 10 ``` * **复杂度分析**： * **时间复杂度**： O（R * C），需要矩阵的单个遍历，因此时间复杂度为 O（R * C）。 * **空间复杂度**：`O(1)`，需要恒定的空间。 **高效方法：** 以螺旋顺序遍历数组时，使用一个循环遍历边。因此，如果可以发现第 k 个元素位于给定的边，则可以在恒定时间内找到第 k 个元素。这可以递归和迭代地完成。 * **算法**： 1. 以螺旋或循环形式遍历矩阵。 2. 因此，一个循环可分为 4 个部分，因此，如果循环的大小为 m X n。 3. 元素在第一行，即 k < = m 4. 元素位于最后一列，即 k < =（m + n-1） 5. 元素位于最后一行，即 k < =（m + n-1 + m-1） 6. 元素在第一列中，即 k < =（m + n-1 + m-1 + n-2） 7. 如果满足上述任何条件，则可以发现第 k 个元素是恒定时间。 8. 否则，从数组中删除循环并递归调用该函数。 * **实现**： ## C++ ``` // C++ program for Kth element in spiral // form of matrix #include <bits/stdc++.h> #define MAX 100 using namespace std; /* function for Kth element */ int findK(int A[MAX][MAX], int n, int m, int k) { if (n < 1 || m < 1) return -1; /*....If element is in outermost ring ....*/ /* Element is in first row */ if (k <= m) return A[0][k - 1]; /* Element is in last column */ if (k <= (m + n - 1)) return A[(k - m)][m - 1]; /* Element is in last row */ if (k <= (m + n - 1 + m - 1)) return A[n - 1][m - 1 - (k - (m + n - 1))]; /* Element is in first column */ if (k <= (m + n - 1 + m - 1 + n - 2)) return A[n - 1 - (k - (m + n - 1 + m - 1))][0]; /*....If element is NOT in outermost ring ....*/ /* Recursion for sub-matrix. &A[1][1] is address to next inside sub matrix.*/ return findK((int(*)[MAX])(&(A[1][1])), n - 2, m - 2, k - (2 * n + 2 * m - 4)); } /* Driver code */ int main() { int a[MAX][MAX] = { { 1, 2, 3, 4, 5, 6 }, { 7, 8, 9, 10, 11, 12 }, { 13, 14, 15, 16, 17, 18 } }; int k = 17; cout << findK(a, 3, 6, k) << endl; return 0; } ``` ## Java ``` // Java program for Kth element in spiral // form of matrix class GFG { static int MAX = 100; /* function for Kth element */ static int findK(int A[][], int i, int j, int n, int m, int k) { if (n < 1 || m < 1) return -1; /*.....If element is in outermost ring ....*/ /* Element is in first row */ if (k <= m) return A[i + 0][j + k - 1]; /* Element is in last column */ if (k <= (m + n - 1)) return A[i + (k - m)][j + m - 1]; /* Element is in last row */ if (k <= (m + n - 1 + m - 1)) return A[i + n - 1][j + m - 1 - (k - (m + n - 1))]; /* Element is in first column */ if (k <= (m + n - 1 + m - 1 + n - 2)) return A[i + n - 1 - (k - (m + n - 1 + m - 1))][j + 0]; /*.....If element is NOT in outermost ring ....*/ /* Recursion for sub-matrix. &A[1][1] is address to next inside sub matrix.*/ return findK(A, i + 1, j + 1, n - 2, m - 2, k - (2 * n + 2 * m - 4)); } /* Driver code */ public static void main(String args[]) { int a[][] = { { 1, 2, 3, 4, 5, 6 }, { 7, 8, 9, 10, 11, 12 }, { 13, 14, 15, 16, 17, 18 } }; int k = 17; System.out.println(findK(a, 0, 0, 3, 6, k)); } } // This code is contributed by Arnab Kundu ``` ## Python3 ``` # Python3 program for Kth element in spiral # form of matrix MAX = 100 ''' function for Kth element ''' def findK(A, n, m, k): if (n < 1 or m < 1): return -1 '''....If element is in outermost ring ....''' ''' Element is in first row ''' if (k <= m): return A[0][k - 1] ''' Element is in last column ''' if (k <= (m + n - 1)): return A[(k - m)][m - 1] ''' Element is in last row ''' if (k <= (m + n - 1 + m - 1)): return A[n - 1][m - 1 - (k - (m + n - 1))] ''' Element is in first column ''' if (k <= (m + n - 1 + m - 1 + n - 2)): return A[n - 1 - (k - (m + n - 1 + m - 1))][0] '''....If element is NOT in outermost ring ....''' ''' Recursion for sub-matrix. &A[1][1] is address to next inside sub matrix.''' A.pop(0) [j.pop(0) for j in A] return findK(A, n - 2, m - 2, k - (2 * n + 2 * m - 4)) ''' Driver code ''' a = [[1, 2, 3, 4, 5, 6],[7, 8, 9, 10, 11, 12 ], [ 13, 14, 15, 16, 17, 18 ]] k = 17 print(findK(a, 3, 6, k)) # This code is contributed by shivanisinghss2110 ``` **输出**： ``` 10 ``` * **复杂度分析**： * **时间复杂度**： O（c），其中 c 是相对于第 k 个元素的外圆环数。 * **空间复杂度**：`O(1)`。由于需要恒定的空间。本文由 **Shashank Mishra（Gullu）**提供。如果您喜欢 GeeksforGeeks 并希望做出贡献，则也可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。