Dada una array cuadrada A[][] de N * N, la tarea es clasificar los elementos de contorno de una array comenzando desde el límite más externo hasta el más interno y colocarlos en el sentido de las agujas del reloj.
Ejemplos:
Entrada: A[][] = {{9, 7, 4, 5}, {1, 6, 2, -6}, {12, 20, 2, 0}, {-5, -6, 7, – 2}}
Salida: {{-6, -6, -5, -2}, {12, 2, 2, 0}, {9, 20, 6, 1}, {7, 7, 5, 4}}
Explicación:
Los elementos de contorno más externos son {9, 7, 4, 5, -6, 0, -2, 7, -6, -5, 12, 1}.
El orden ordenado de los elementos de contorno es {-6, -6, -5, -2, 0, 1, 4, 5, 7, 7, 9, 12}.
Al colocar esta secuencia ordenada de elementos nuevamente en la array en el sentido de las agujas del reloj, comenzando desde la esquina superior izquierda, se modifica A[][] a {{-6, -6, -5, -2}, {12, 6, 2, 0}, {9, 20, 2, 1}, {7, 7, 5, 4}}
El siguiente nivel de elementos de contorno son {6, 2, 2, 20}.
El orden ordenado de estos elementos es {2, 2, 6, 20}.
Al colocar esta secuencia ordenada de elementos nuevamente en la array en el sentido de las agujas del reloj, comenzando desde la esquina superior izquierda, se modifica A[][] a {{-6, -6, -5, -2}, {12, 2, 2, 0}, {9, 20, 6, 1}, {7, 7, 5, 4}}Entrada: A[][] = {{4, 3,}, {1, 2}}
Salida: {{1, 2,}, {4, 3}}
Enfoque: la idea es utilizar variables de contorno para obtener los elementos de contorno actuales y almacenarlos en una array. Luego, ordene la array en orden ascendente y coloque los elementos ordenados nuevamente en la array en el sentido de las agujas del reloj.
Siga los pasos a continuación para resolver el problema:
- Inicialice las variables, digamos k, m, l y n , que representan el índice de la fila inicial, el índice de la fila final, el índice de la columna inicial y el índice de la columna final.
- Iterar hasta que se visiten todos los cuadrados de bucles.
- En cada recorrido del bucle exterior, almacene los elementos del cuadrado en una array, digamos V , en el sentido de las agujas del reloj.
- Empuje la fila superior en V , es decir, empuje los elementos de la k -ésima fila de los índices de columna l a n . Aumente la cuenta de k .
- Empuje la columna de la derecha en V , es decir, empuje los elementos de la columna n – 1 de los índices de fila k a m . Disminuir el conteo de n .
- Empuje la fila inferior, es decir, si k < m , luego empuje los elementos de la fila m-1 de los índices de columna n – 1 a l . Disminuya la cuenta de m .
- Empuje la columna de la izquierda, es decir, si l < n , luego empuje los elementos de la l -ésima columna desde los índices de fila m – 1 hasta k . Aumentar la cuenta de l .
- Ordene la array V en orden ascendente .
- Repita los pasos anteriores y actualice los elementos de la array con los elementos ordenados de V .
- Después de completar el recorrido de la array, imprima la array A modificada .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the elements
// of the matrix in row-wise manner
void printMatrix(vector<vector<int> > a)
{
for (auto x : a) {
for (auto y : x) {
cout << y << " ";
}
cout << "\n";
}
}
// Function to sort boundary elements
// of a matrix starting from the outermost
// to the innermost boundary and place them
// in a clockwise manner
void sortBoundaryWise(vector<vector<int> > a)
{
/* k - starting row index
m - ending row index
l - starting column index
n - ending column index
i - iterator
*/
int i, k = 0, l = 0;
int m = a.size(), n = a[0].size();
int n_i, n_k = 0, n_l = 0, n_m = m, n_n = n;
while (k < m && l < n) {
// Stores the current
// boundary elements
vector<int> boundary;
// Push the first row
for (i = l; i < n; ++i) {
boundary.push_back(a[k][i]);
}
k++;
// Push the last column
for (i = k; i < m; ++i) {
boundary.push_back(a[i][n - 1]);
}
n--;
// Push the last row
if (k < m) {
for (i = n - 1; i >= l; --i) {
boundary.push_back(a[m - 1][i]);
}
m--;
}
// Push the first column
if (l < n) {
for (i = m - 1; i >= k; --i) {
boundary.push_back(a[i][l]);
}
l++;
}
// Sort the boundary elements
sort(boundary.begin(), boundary.end());
int ind = 0;
// Update the current boundary
// with sorted elements
// Update the first row
for (i = n_l; i < n_n; ++i) {
a[n_k][i] = boundary[ind++];
}
n_k++;
// Update the last column
for (i = n_k; i < n_m; ++i) {
a[i][n_n - 1] = boundary[ind++];
}
n_n--;
// Update the last row
if (n_k < n_m) {
for (i = n_n - 1; i >= n_l; --i) {
a[n_m - 1][i] = boundary[ind++];
}
n_m--;
}
// Update the first column
if (n_l < n_n) {
for (i = n_m - 1; i >= n_k; --i) {
a[i][n_l] = boundary[ind++];
}
n_l++;
}
}
// Print the resultant matrix
printMatrix(a);
}
// Driver Code
int main()
{
// Given matrix
vector<vector<int> > matrix = { { 9, 7, 4, 5 },
{ 1, 6, 2, -6 },
{ 12, 20, 2, 0 },
{ -5, -6, 7, -2 } };
sortBoundaryWise(matrix);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print the elements
// of the matrix in row-wise manner
static void printMatrix(ArrayList<ArrayList<Integer>> a)
{
for(int i = 0; i < a.size(); i++)
{
for(int j = 0; j < a.get(i).size(); j++)
{
System.out.print(a.get(i).get(j) + " ");
}
System.out.println();
}
}
// Function to sort boundary elements
// of a matrix starting from the outermost
// to the innermost boundary and place them
// in a clockwise manner
static void sortBoundaryWise(ArrayList<ArrayList<Integer>> a)
{
/* k - starting row index
m - ending row index
l - starting column index
n - ending column index
i - iterator
*/
int i, k = 0, l = 0;
int m = a.size(), n = a.get(0).size();
int n_i, n_k = 0, n_l = 0, n_m = m, n_n = n;
while (k < m && l < n)
{
// Stores the current
// boundary elements
ArrayList<Integer> boundary = new ArrayList<Integer>();
// Push the first row
for(i = l; i < n; ++i)
{
boundary.add(a.get(k).get(i));
}
k++;
// Push the last column
for(i = k; i < m; ++i)
{
boundary.add(a.get(i).get(n - 1));
}
n--;
// Push the last row
if (k < m)
{
for(i = n - 1; i >= l; --i)
{
boundary.add(a.get(m - 1).get(i));
}
m--;
}
// Push the first column
if (l < n)
{
for(i = m - 1; i >= k; --i)
{
boundary.add(a.get(i).get(l));
}
l++;
}
// Sort the boundary elements
Collections.sort(boundary);
int ind = 0;
// Update the current boundary
// with sorted elements
// Update the first row
for(i = n_l; i < n_n; ++i)
{
a.get(n_k).set(i, boundary.get(ind));
ind++;
}
n_k += 1;
// Update the last column
for(i = n_k; i < n_m; ++i)
{
a.get(i).set(n_n - 1, boundary.get(ind));
ind++;
}
n_n--;
// Update the last row
if (n_k < n_m)
{
for(i = n_n - 1; i >= n_l; --i)
{
a.get(n_m - 1).set(i, boundary.get(ind));
ind++;
}
n_m--;
}
// Update the first column
if (n_l < n_n)
{
for(i = n_m - 1; i >= n_k; --i)
{
a.get(i).set(n_l, boundary.get(ind));
ind++;
}
n_l++;
}
}
// Print the resultant matrix
printMatrix(a);
}
// Driver Code
public static void main(String args[])
{
// Given matrix
ArrayList<
ArrayList<Integer>> matrix = new ArrayList<
ArrayList<Integer>>();
ArrayList<Integer> list1 = new ArrayList<Integer>(
Arrays.asList(9, 7, 4, 5));
ArrayList<Integer> list2 = new ArrayList<Integer>(
Arrays.asList(1, 6, 2, -6));
ArrayList<Integer> list3 = new ArrayList<Integer>(
Arrays.asList(12, 20, 2, 0));
ArrayList<Integer> list4 = new ArrayList<Integer>(
Arrays.asList(-5, -6, 7, -2));
matrix.add(list1);
matrix.add(list2);
matrix.add(list3);
matrix.add(list4);
sortBoundaryWise(matrix);
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program for the above approach # Function to print the elements # of the matrix in row-wise manner def printMatrix(a): for x in a: for y in x: print(y, end = " ") print() # Function to sort boundary elements # of a matrix starting from the outermost # to the innermost boundary and place them # in a clockwise manner def sortBoundaryWise(a): ''' k - starting row index m - ending row index l - starting column index n - ending column index i - iterator ''' k = 0 l = 0 m = len(a) n = len(a[0]) n_k = 0 n_l = 0 n_m = m n_n = n while (k < m and l < n): # Stores the current # boundary elements boundary = [] # Push the first row for i in range(l, n): boundary.append(a[k][i]) k += 1 # Push the last column for i in range(k, m): boundary.append(a[i][n - 1]) n -= 1 # Push the last row if (k < m): for i in range(n - 1, l - 1, -1): boundary.append(a[m - 1][i]) m -= 1 # Push the first column if (l < n): for i in range(m - 1, k - 1, -1): boundary.append(a[i][l]) l += 1 # Sort the boundary elements boundary.sort() ind = 0 # Update the current boundary # with sorted elements # Update the first row for i in range(n_l, n_n): a[n_k][i] = boundary[ind] ind += 1 n_k += 1 # Update the last column for i in range(n_k, n_m): a[i][n_n - 1] = boundary[ind] ind += 1 n_n -= 1 # Update the last row if (n_k < n_m): for i in range(n_n - 1, n_l - 1, -1): a[n_m - 1][i] = boundary[ind] ind += 1 n_m -= 1 # Update the first column if (n_l < n_n): for i in range(n_m - 1, n_k - 1, -1): a[i][n_l] = boundary[ind] ind += 1 n_l += 1 # Print the resultant matrix printMatrix(a) # Driver Code if __name__ == "__main__": # Given matrix matrix = [[9, 7, 4, 5], [1, 6, 2, -6], [12, 20, 2, 0], [-5, -6, 7, -2]] sortBoundaryWise(matrix) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to print the elements
// of the matrix in row-wise manner
static void printMatrix(List<List<int>> a)
{
foreach(List<int> x in a) {
foreach(int y in x) {
Console.Write(y + " ");
}
Console.WriteLine();
}
}
// Function to sort boundary elements
// of a matrix starting from the outermost
// to the innermost boundary and place them
// in a clockwise manner
static void sortBoundaryWise(List<List<int>> a)
{
/* k - starting row index
m - ending row index
l - starting column index
n - ending column index
i - iterator
*/
int i, k = 0, l = 0;
int m = a.Count, n = a[0].Count;
int n_k = 0, n_l = 0, n_m = m, n_n = n;
while (k < m && l < n) {
// Stores the current
// boundary elements
List<int> boundary = new List<int>();
// Push the first row
for (i = l; i < n; ++i) {
boundary.Add(a[k][i]);
}
k++;
// Push the last column
for (i = k; i < m; ++i) {
boundary.Add(a[i][n - 1]);
}
n--;
// Push the last row
if (k < m) {
for (i = n - 1; i >= l; --i) {
boundary.Add(a[m - 1][i]);
}
m--;
}
// Push the first column
if (l < n) {
for (i = m - 1; i >= k; --i) {
boundary.Add(a[i][l]);
}
l++;
}
// Sort the boundary elements
boundary.Sort();
int ind = 0;
// Update the current boundary
// with sorted elements
// Update the first row
for (i = n_l; i < n_n; ++i) {
a[n_k][i] = boundary[ind++];
}
n_k++;
// Update the last column
for (i = n_k; i < n_m; ++i) {
a[i][n_n - 1] = boundary[ind++];
}
n_n--;
// Update the last row
if (n_k < n_m) {
for (i = n_n - 1; i >= n_l; --i) {
a[n_m - 1][i] = boundary[ind++];
}
n_m--;
}
// Update the first column
if (n_l < n_n) {
for (i = n_m - 1; i >= n_k; --i) {
a[i][n_l] = boundary[ind++];
}
n_l++;
}
}
// Print the resultant matrix
printMatrix(a);
}
// Driver code
static void Main()
{
// Given matrix
List<List<int>> matrix = new List<List<int>>();
matrix.Add(new List<int>(new int[]{9, 7, 4, 5}));
matrix.Add(new List<int>(new int[]{1, 6, 2, -6}));
matrix.Add(new List<int>(new int[]{12, 20, 2, 0}));
matrix.Add(new List<int>(new int[]{-5, -6, 7, -2}));
sortBoundaryWise(matrix);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// JavaScript program for the above approach
// Function to print the elements
// of the matrix in row-wise manner
function printMatrix(a)
{
for(let i = 0; i < a.length; i++)
{
for(let j = 0; j < a[i].length; j++)
{
document.write(a[i][j] + " ");
}
document.write("<br>");
}
}
// Function to sort boundary elements
// of a matrix starting from the outermost
// to the innermost boundary and place them
// in a clockwise manner
function sortBoundaryWise(a)
{
/* k - starting row index
m - ending row index
l - starting column index
n - ending column index
i - iterator
*/
let i, k = 0, l = 0;
let m = a.length, n = a[0].length;
let n_i, n_k = 0, n_l = 0, n_m = m, n_n = n;
while (k < m && l < n)
{
// Stores the current
// boundary elements
let boundary = [];
// Push the first row
for(i = l; i < n; ++i)
{
boundary.push(a[k][i]);
}
k++;
// Push the last column
for(i = k; i < m; ++i)
{
boundary.push(a[i][n - 1]);
}
n--;
// Push the last row
if (k < m)
{
for(i = n - 1; i >= l; --i)
{
boundary.push(a[m - 1][i]);
}
m--;
}
// Push the first column
if (l < n)
{
for(i = m - 1; i >= k; --i)
{
boundary.push(a[i][l]);
}
l++;
}
// Sort the boundary elements
boundary.sort(function(a,b){return a-b;});
let ind = 0;
// Update the current boundary
// with sorted elements
// Update the first row
for(i = n_l; i < n_n; ++i)
{
a[n_k][i] = boundary[ind];
ind++;
}
n_k += 1;
// Update the last column
for(i = n_k; i < n_m; ++i)
{
a[i][n_n - 1] = boundary[ind];
ind++;
}
n_n--;
// Update the last row
if (n_k < n_m)
{
for(i = n_n - 1; i >= n_l; --i)
{
a[n_m - 1][i] = boundary[ind];
ind++;
}
n_m--;
}
// Update the first column
if (n_l < n_n)
{
for(i = n_m - 1; i >= n_k; --i)
{
a[i][n_l] = boundary[ind];
ind++;
}
n_l++;
}
}
// Print the resultant matrix
printMatrix(a);
}
// Driver Code
// Given matrix
let matrix = [];
let list1 = [9, 7, 4, 5];
let list2=[1, 6, 2, -6];
let list3=[12, 20, 2, 0];
let list4=[-5, -6, 7, -2];
matrix.push(list1);
matrix.push(list2);
matrix.push(list3);
matrix.push(list4);
sortBoundaryWise(matrix);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
-6 -6 -5 -2 12 2 2 0 9 20 6 1 7 7 5 4
Complejidad de tiempo: O(N 3 *log(N))
Espacio auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por ajaykr00kj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA