以矩阵的螺旋形式打印第K个元素
原文： 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\.
简单方法：一种简单的解决方案是开始以螺旋形式遍历矩阵打印螺旋矩阵并启动计数器，即count = 0。只要count等于K，就打印该元素。
-
算法：
-
保持变量
count = 0以存储计数。 -
从头到尾遍历矩阵。
-
每次迭代将计数增加 1。
-
如果计数等于
k的给定值，则打印该元素并中断。
-
-
实现：
C++
```
include
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个元素。 这可以递归和迭代地完成。
-
算法：
-
以螺旋或循环形式遍历矩阵。
-
因此，一个循环可分为 4 个部分，因此，如果循环的大小为
m X 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
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)。由于需要恒定的空间。
-
版权属于：月萌API www.moonapi.com，转载请注明出处
