以矩陣的螺旋形式打印第 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。