Clasificación de los elementos de contorno de una array

Dada una array mat[][] de tamaño M*N , la tarea es ordenar solo los elementos del borde de la array en el sentido de las agujas del reloj e imprimir la array después de ordenar nuevamente.

Ejemplos: 
 

Entrada: M = 4, N = 5, A continuación se muestra la array dada: 

1 2 3 4 0 
1 1 1 1 2  
1 2 2 2 4 
1 9 3 1 7

Salida: 
0 1 1 1 1 
9 1 1 1 1 
7 2 2 2 2 
4 4 3 3 2 
Explicación: 
Para una array dada, los elementos del borde son: 
(1, 2, 3, 4, 0, 2, 4, 7, 1 , 3, 9, 1, 1, 1) 
Después de ordenar en el sentido de las agujas del reloj: 
(0, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 7, 9)

Entrada: M = 3, N = 4 

4 2 8 0 
2 6 9 8 
0 3 1 7

Salida: 
0 0 1 2 
8 6 9 2 
8 7 4 3 
Explicación: 
Para una array dada, los elementos del borde son: 
(4, 2, 8, 0, 8, 7, 1, 3, 0, 2) 
Después de ordenar en el sentido de las agujas del reloj : 
(0, 0, 1, 2, 2, 3, 4, 7, 8, 8) 
 

Enfoque: la idea es almacenar todos los elementos de borde de la array dada en una array y ordenar esta array y luego simplemente imprimir la nueva array usando esta array ordenada como elementos de borde.

Los pasos detallados son los siguientes:  

• Atraviese la array dada y empuje todos los elementos de contorno a una array A[] .
• Ordene la array A[] en orden ascendente.
• Imprima la primera fila usando los primeros N elementos de la array A[] .
• Desde la segunda fila hasta la penúltima fila, primero imprima un solo elemento desde el final de A[] , luego imprima N-2 elementos intermedios desde la array original y finalmente un solo elemento desde el frente de A[] .
• Para la última fila, imprima los elementos intermedios de A[] que aún no se impriman, en orden inverso.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
void printMatrix(int grid[][5], int m, int n)
{
  vector<int> A;
 
  // Appending border elements
  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j < n; j++)
    {
      if (j == n - 1 || (i == m - 1) || j == 0
          || i == 0)
        A.push_back(grid[i][j]);
    }
  }
 
  // Sorting the list
  sort(A.begin(), A.end());
 
  // Printing first row with
  // first N elements from A
  for (int i = 0; i < n; i++)
    cout << A[i] << " ";
  cout << endl;
  // print(*A[:n])
 
  // Printing N-2 rows
  for (int i = 0; i < m - 2; i++)
  {
 
    // Print elements from last
    cout << A[A.size() - i - 1] << " ";
 
    // Print middle elements
    // from original matrix
    for (int j = 1; j < n - 1; j++)
      cout << grid[i + 1][j] << " ";
 
    // Print elements from front
    cout << (A[n + i]) << endl;
  }
 
  // Printing last row
  reverse(A.begin() + n + m - 2,
          A.begin() + n + m + n - 2);
  for (int i = n + m - 2; i < n + m - 2 + n; i++)
    cout << A[i] << " ";
  //[n + m - 2:n + m - 2 + n] << endl;
}
 
// Driver Code
int main()
{
  // Dimensions of a Matrix
  int m = 4, n = 5;
 
  // Given Matrix
  int grid[][5] = { { 1, 2, 3, 4, 0 },
                   { 1, 1, 1, 1, 2 },
                   { 1, 2, 2, 2, 4 },
                   { 1, 9, 3, 1, 7 } };
 
  // Function Call
  printMatrix(grid, m, n);
  return 0;
}
 
// This code is contributed by chitranayal.

// JAVA program for the above approach
import java.util.*;
class GFG
{
 
  public static void printMatrix(int[][] grid, int m, int n)
  {
    ArrayList<Integer> A = new ArrayList<>();
 
    // Appending border elements
    for (int i = 0; i < m; i++)
    {
      for (int j = 0; j < n; j++)
      {
        if (j == n - 1 || (i == m - 1) || j == 0
            || i == 0)
          A.add(grid[i][j]);
      }
    }
 
    // Sorting the list
    Collections.sort(A);  
 
    // Printing first row with
    // first N elements from A
    for (int i = 0; i < n; i++)
      System.out.print(A.get(i)+" ");
    System.out.print('\n');
    // print(*A[:n])
 
    // Printing N-2 rows
    for (int i = 0; i < m - 2; i++)
    {
 
      // Print elements from last
      System.out.print(A.get(A.size() - i - 1)+" ");
 
      // Print middle elements
      // from original matrix
      for (int j = 1; j < n - 1; j++)
        System.out.print(grid[i + 1][j]+" ");
 
      // Print elements from front
      System.out.println(A.get(n + i));
    }
 
    // Printing last row
    Collections.reverse(A.subList( n + m - 2 , n + m - 2 + n ) ) ;
    for (int i = n + m - 2; i < n + m - 2 + n; i++)
      System.out.print(A.get(i)+" ");
 
    //[n + m - 2:n + m - 2 + n] << endl;
  }
 
  /* Driver program to test above function */
  public static void main(String[] args)
  {
    // Dimensions of a Matrix
    int m = 4, n = 5;
 
    // Given Matrix
    int[][] grid = { { 1, 2, 3, 4, 0 },
                    { 1, 1, 1, 1, 2 },
                    { 1, 2, 2, 2, 4 },
                    { 1, 9, 3, 1, 7 } };
 
    // Function Call
    printMatrix(grid, m, n);
  }
}
 
// This code is contributed by Pushpesh Raj.

# Python program for the above approach
 
def printMatrix(grid, m, n):
     
    A =[]
 
    # Appending border elements
    for i in range(m):
        for j in range(n):
            if j == n-1 or (i == m-1
                ) or j == 0 or i == 0:
                A.append(grid[i][j])
                 
    # Sorting the list
     
    A.sort()
 
 
    # Printing first row with
    # first N elements from A
    print(*A[:n])
 
 
    # Printing N-2 rows
    for i in range(m-2):
         
        # Print elements from last
        print(A[len(A)-i-1],
                          end =" ")
        # Print middle elements
        # from original matrix
        for j in range(1, n-1):
            print(grid[i + 1][j],
                          end =" ")
             
             
        # Print elements from front
        print(A[n + i])
 
    # Printing last row
    print(*reversed(A[n + m-2:n + m-2 + n]))
 
# Driver Code
 
# Dimensions of a Matrix
m, n = 4, 5
 
# Given Matrix
grid =[[1, 2, 3, 4, 0],
       [1, 1, 1, 1, 2],
       [1, 2, 2, 2, 4],
       [1, 9, 3, 1, 7]]
 
# Function Call
printMatrix(grid, m, n)

<script>
 
// Javascript program for the above approach
function printMatrix(grid, m, n)
{
    let A = [];
     
    // Appending border elements
    for(let i = 0; i < m; i++)
    {
        for(let j = 0; j < n; j++)
        {
            if (j == n - 1 || (i == m - 1) ||
                j == 0 || i == 0)
                A.push(grid[i][j]);
        }
    }
     
    // Sorting the list
    A.sort(function(a, b){return a - b;});
     
    // Printing first row with
    // first N elements from A
    for(let i = 0; i < n; i++)
        document.write(A[i] + " ");
         
    document.write("<br>")
    // print(*A[:n])
     
    // Printing N-2 rows
    for(let i = 0; i < m - 2; i++)
    {
     
        // Print elements from last
        document.write(A[A.length - i - 1] + " ");
         
        // Print middle elements
        // from original matrix
        for(let j = 1; j < n - 1; j++)
            document.write(grid[i + 1][j] + " ");
         
        // Print elements from front
        document.write(A[n + i] + "<br>")
    }
     
    // Printing last row
    document.write(A.slice(
        n + m - 2, n + m - 2 + n).reverse().join(" "));
    //[n + m - 2:n + m - 2 + n] << endl;
}
 
// Driver Code
 
// Dimensions of a Matrix
let m = 4, n = 5;
 
// Given Matrix
let grid = [ [ 1, 2, 3, 4, 0 ],
             [ 1, 1, 1, 1, 2 ],
             [ 1, 2, 2, 2, 4 ],
             [ 1, 9, 3, 1, 7 ] ];
                    
// Function Call
printMatrix(grid, m, n);
   
// This code is contributed by avanitrachhadiya2155
 
</script>

0 1 1 1 1
9 1 1 1 1
7 2 2 2 2
4 4 3 3 2

Complejidad temporal: O(M*N)  
Espacio auxiliar: O(M+N)