给定一个nxm阶的二维矩阵，以矩阵的螺旋形式打印第K个元素。请参见以下示例。 例如：
null
Input: mat[][] = {{1, 2, 3, 4} {5, 6, 7, 8} {9, 10, 11, 12} {13, 14, 15, 16}} k = 6Output: 12Explanation: The elements in spiral order is 1, 2, 3, 4, 8, 12, 16, 15...so the 6th element is 12Input: mat[][] = {{1, 2, 3, 4, 5, 6} {7, 8, 9, 10, 11, 12} {13, 14, 15, 16, 17, 18}} k = 17Output: 10Explanation: 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.
简单方法： 一个简单的解决方案是开始以螺旋形式遍历矩阵 打印螺旋矩阵 并启动一个计数器，即；计数=0。每当count等于K时，打印该元素。
- 算法：
- 保留一个变量 计数=0 来存储计数。
- 从开始到结束，以螺旋方式遍历矩阵。
- 每次迭代将计数增加1。
- 如果计数等于给定的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 |
C#
using System; 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) Console.WriteLine(a[k, i] + " " ); } k++; /* check the last column from the remaining columns */ for (i = k; i < m; ++i) { count++; if (count == c) Console.WriteLine(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) Console.WriteLine(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) Console.WriteLine(a[i, l] + " " ); } l++; } } } // Driver code static void Main() { 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 divyeshrabadiya07. |
Javascript
<script> let R = 3; let C = 6; function spiralPrint(m, n, a, c) { let i, k = 0, l = 0; let 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) document.write(a[k][i] + " " ); } k++; /* check the last column from the remaining columns */ for (i = k; i < m; ++i) { count++; if (count == c) document.write(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) document.write(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) document.write(a[i][l] + " " ); } l++; } } } let 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); </script> |
输出：
10
复杂性分析：
- 时间复杂性： O（R*C），需要对矩阵进行一次遍历，因此时间复杂度为O（R*C）。
- 空间复杂性： O（1），需要恒定的空间。
有效方法： 以螺旋顺序遍历阵列时，会使用一个循环遍历两侧。因此，如果可以发现第k个元素在给定的一侧，那么第k个元素可以在恒定的时间内找到。这既可以递归地进行，也可以迭代地进行。
- 算法：
- 以螺旋或循环的形式遍历矩阵。
- 所以一个循环可以分为4部分，如果循环的大小是m×n。
- 元素位于第一行，即k<=m
- 元素位于最后一列，即k<=（m+n-1）
- 元素位于最后一行，即k<=（m+n-1+m-1）
- 元素位于第一列，即k<=（m+n-1+m-1+n-2）
- 如果上述任何条件满足，则可以找到常数时间的第k个元素。
- 否则，从数组中删除循环并递归调用该函数。
- 实施：
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 |
C#
// C# program for Kth element in spiral // form of matrix using System; class GFG { /* 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 static void Main() { int [,] a = { { 1, 2, 3, 4, 5, 6 }, { 7, 8, 9, 10, 11, 12 }, { 13, 14, 15, 16, 17, 18 } }; int k = 17; Console.WriteLine(findK(a, 0, 0, 3, 6, k)); } } // This code is contributed by divyesh072019. |
Javascript
<script> // JavaScript program for Kth element in spiral // form of matrix let MAX = 100; /* function for Kth element */ function findK(A,i,j,n,m,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 */ let a = [[ 1, 2, 3, 4, 5, 6 ], [ 7, 8, 9, 10, 11, 12 ], [ 13, 14, 15, 16, 17, 18 ]]; let k = 17; document.write(findK(a, 0, 0, 3, 6, k)); // This code is contributed by sravan kumar </script> |
输出：
10
复杂性分析：
- 时间复杂性： O（c），其中c是关于第k元素的外圆环数。
- 空间复杂性： O（1）。 因为需要恒定的空间。
本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
