Dada una Array 2D de orden n X m, imprima el elemento K’th en la forma espiral de la array. Vea los siguientes ejemplos.
Ejemplos:
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.
Enfoque simple: una solución simple es comenzar a atravesar la array en forma de espiral Imprimir array en espiral y comenzar un contador, es decir; count = 0. Cada vez que count sea igual a K, imprima ese elemento.
- Algoritmo:
- Mantenga una cuenta variable = 0 para almacenar la cuenta.
- Atraviesa la array en espiral de principio a fin.
- Aumente el conteo en 1 por cada iteración.
- Si el conteo es igual al valor dado de k, imprima el elemento y rompa.
Implementación:
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>
Producción
10
Análisis de Complejidad:
- Complejidad de tiempo: O(R*C), Se necesita un solo recorrido de array para que la Complejidad de tiempo sea O(R*C).
- Complejidad espacial: O(1), se requiere espacio constante.
Enfoque eficiente: al atravesar la array en orden espiral, se utiliza un bucle para atravesar los lados. Entonces, si se puede encontrar que el k-ésimo elemento está en el lado dado, entonces el k-ésimo elemento se puede encontrar en tiempo constante. Esto se puede hacer tanto de forma recursiva como iterativa.
- Algoritmo:
- Atraviesa la array en forma de espiral o ciclos.
- Entonces, un ciclo se puede dividir en 4 partes, por lo que si el ciclo es de tamaño m X n.
- El elemento está en la primera fila, es decir, k <= m
- El elemento está en la última columna, es decir, k <= (m+n-1)
- El elemento está en la última fila, es decir, k <= (m+n-1+m-1)
- El elemento está en la primera columna, es decir, k <= (m+n-1+m-1+n-2)
- Si alguna de las condiciones anteriores se cumple, entonces el k-ésimo elemento se puede encontrar en tiempo constante.
- De lo contrario, elimine el ciclo de la array y llame recursivamente a la función.
Implementación:
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>
Producción
10
Análisis de Complejidad:
- Complejidad temporal: O(c), donde c es el número de anillos circulares exteriores con respecto al k’ésimo elemento.
- Complejidad espacial: O(1).
Como se requiere espacio constante.
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA