Dada una array 2D arr[] que tiene N filas de tamaño variable, la tarea es ordenar la array en orden lexicográfico, es decir, ordenar lexicográficamente cada fila y luego ordenar esas filas ordenadas.
Ejemplos:
Entrada: arr[][] = { {23}, {59}, {23, 59} }
Salida: { {23}, {23, 59}, {59} }
Explicación: Las filas están ordenadas lexicográficamente.
Aquí, la fila {23, 59} es lexicográficamente más pequeña que {59}
porque el primer elemento (23) es más pequeño que 59.
Aunque {23} y {23, 59} tienen 23 como primer elemento, {23} solo tiene un elemento
Por lo tanto, {23} es lexicográficamente más pequeño que {23, 59}Entrada: arr[][] ={ {3, 2, 5, 6}, {1, 2, 3}, {6, 3}, {5, 4, 2} } Salida: { {1, 2
, 3 }, {2, 3, 5, 6}, {2, 4, 5}, {3, 6} }Entrada: arr[][] = { {3, 2, 5, 6}, {, 2, 3, 5}, {2, 4, 2, 1}, {6, 3, 7, 8} } Salida
: { {1, 2, 2, 4}, {1, 2, 3, 5}, {2, 3, 5, 6}, {3, 6, 7, 8} }
Planteamiento: La idea para resolver el problema es la siguiente:
El orden lexicográfico más pequeño se puede obtener ordenando los elementos de cada fila y luego ordenando toda la array 2D según el orden lexicográfico de los elementos en cada fila.
Siga los pasos a continuación para resolver este problema:
- Primero, ordene lexicográficamente cada fila de la array 2D dada.
- Ordene toda la array 2D según el orden lexicográfico de los elementos de cada fila. La fila que sea lexicográficamente más pequeña llegará primero en la array ordenada.
- Imprima la array 2D.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to sort the 2D array // lexicographically void sort_lexicographically(vector<vector<int> >& arr) { for (int i = 0; i < arr.size(); ++i) { // Initially sorting the array row-wise sort(arr[i].begin(), arr[i].end()); } // Sort the whole array in lexicographically sort(arr.begin(), arr.end()); } // Driver's code int main() { vector<vector<int> > arr = { { 3, 2, 5, 6 }, { 1, 2, 3 }, { 5, 4, 2 }, { 6, 3 }, { 9, 99 }, { 6, 3, 2 } }; sort_lexicographically(arr); // Resultant 2-d array after // sorting lexicographically for (int i = 0; i < arr.size(); ++i) { for (int j = 0; j < arr[i].size(); ++j) { cout << arr[i][j] << " "; } cout << endl; } return 0; }
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to sort the 2D array // lexicographically public static void sort_lexicographically(int arr[][]) { for (int i = 0; i < arr.length; ++i) { // Initially sorting the array row-wise Arrays.sort(arr[i]); } // Sort the whole array in lexicographically Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0])); } // Driver Code public static void main(String[] args) { int arr[][] = { { 3, 2, 5, 6 }, { 1, 2, 3 }, { 6, 3 }, { 9, 99 }, { 6, 3, 2 }, { 5, 4, 2 } }; sort_lexicographically(arr); // Resultant 2-d array after // sorting lexicographically for (int i = 0; i < arr.length; ++i) { for (int j = 0; j < arr[i].length; ++j) { System.out.print(arr[i][j] + " "); } System.out.println(); } } } // This code is contributed by Rohit Pradhan
Python3
# Python program for above approach # Function to sort the 2D array # lexicographically def sort_lexicographically(arr) : for i in range(0, len(arr)) : # Initially sorting the array row-wise arr[i].sort() # Sort the whole array in lexicographically arr.sort() # Driver code if __name__ == "__main__": arr = [[ 3, 2, 5, 6 ], [ 1, 2, 3 ], [ 5, 4, 2 ], [ 6, 3 ], [ 9, 99 ], [ 6, 3, 2 ]] sort_lexicographically(arr) # Resultant 2-d array after # sorting lexicographically for i in range(0, len(arr)) : for j in range(0, len(arr[i])) : print(arr[i][j] , end = " ") print() # This code is contributed by code_hunt.
C#
// C# program to implement above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to sort the 2D array // lexicographically public static void sort_lexicographically(int[][] arr) { for (int i = 0 ; i < arr.Length ; ++i) { // Initially sorting the array row-wise Array.Sort(arr[i]); } // Sort the whole array in lexicographically Array.Sort(arr, new comp()); } public static void Main(string[] args){ int[][] arr = new int[][]{ new int[]{ 3, 2, 5, 6 }, new int[]{ 1, 2, 3 }, new int[]{ 6, 3 }, new int[]{ 9, 99 }, new int[]{ 6, 3, 2 }, new int[]{ 5, 4, 2 } }; sort_lexicographically(arr); // Resultant 2-d array after // sorting lexicographically for (int i = 0 ; i < arr.Length ; ++i) { for (int j = 0 ; j < arr[i].Length ; ++j) { Console.Write(arr[i][j] + " "); } Console.WriteLine(""); } } } class comp : IComparer<int[]>{ public int Compare(int[] a1, int[] a2){ return a1[0]-a2[0]; } } // This code is contributed by subhamgoyal2014.
Javascript
<script> // JavaScript code to implement the approach // Function to sort the 2D array // lexicographically function sort_lexicographically(arr) { for (var i = 0; i < arr.length; i++) // Initially sorting the array row-wise arr[i].sort(); // Sort the whole array in lexicographically arr.sort(); } // Driver's code arr = [ [ 3, 2, 5, 6 ], [ 1, 2, 3 ], [ 5, 4, 2 ], [ 6, 3 ], [ 9, 99 ], [ 6, 3, 2 ]]; sort_lexicographically(arr); // Resultant 2-d array after // sorting lexicographically for (var i = 0; i < arr.length; ++i) { for (var j = 0; j < arr[i].length; ++j) { document.write(arr[i][j] + " "); } document.write("\n"); } // This code is contributed by phasing17 </script>
1 2 3 2 3 5 6 2 3 6 2 4 5 3 6 9 99
Complejidad del tiempo:
Espacio Auxiliar:
Publicación traducida automáticamente
Artículo escrito por mkrishnasai y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA