Reorganizar una lista dada de manera que consista en elementos máximos mínimos alternos
#practiceLinkDiv { mostrar: ninguno !importante; } Dada una lista de números enteros, reorganice la lista de manera que consista en elementos mínimos máximos alternos. usando solo operaciones de lista . El primer elemento de la lista debe ser el mínimo y el segundo elemento debe ser el máximo de todos los elementos presentes en la lista. De manera similar, el tercer elemento será el siguiente elemento mínimo y el cuarto elemento será el siguiente elemento máximo, y así sucesivamente. No se permite el uso de espacio extra. Ejemplos:
Input: [1 3 8 2 7 5 6 4]
Output: [1 8 2 7 3 6 4 5]
Input: [1 2 3 4 5 6 7]
Output: [1 7 2 6 3 5 4]
Input: [1 6 2 5 3 4]
Output: [1 6 2 5 3 4]
Recommended Practice Reorganizar la matriz ¡Pruébalo!La idea es ordenar la lista primero en orden ascendente. Luego comenzamos a extraer elementos del final de la lista y los insertamos en su posición correcta en la lista. A continuación se muestra la implementación de la idea anterior:
C++Java// C++ program to rearrange a given list such that it // consists of alternating minimum maximum elements #includeusing namespace std ; // Function to rearrange a given list such that it // consists of alternating minimum maximum elements void alternateSort ( list < int >& inp ) { // sort the list in ascending order inp . sort (); // get iterator to first element of the list list < int >:: iterator it = inp . begin (); it ++ ; for ( int i = 1 ; i < ( inp . size () + 1 ) / 2 ; i ++ ) { // pop last element (next greatest) int val = inp . back (); inp . pop_back (); // insert it after next minimum element inp . insert ( it val ); // increment the pointer for next pair ++ it ; } } // Driver code int main () { // input list list < int > inp ({ 1 3 8 2 7 5 6 4 }); // rearrange the given list alternateSort ( inp ); // print the modified list for ( int i : inp ) cout < < i < < ' ' ; return 0 ; } Python// Java program to rearrange a given list such that it // consists of alternating minimum maximum elements import java.util.* ; class AlternateSort { // Function to rearrange a given list such that it // consists of alternating minimum maximum elements // using LinkedList public static void alternateSort ( LinkedList < Integer > ll ) { Collections . sort ( ll ); for ( int i = 1 ; i < ( ll . size () + 1 ) / 2 ; i ++ ) { Integer x = ll . getLast (); ll . removeLast (); ll . add ( 2 * i - 1 x ); } System . out . println ( ll ); } public static void main ( String [] args ) throws java . lang . Exception { // input list Integer arr [] = { 1 3 8 2 7 5 6 4 }; // convert array to LinkedList LinkedList < Integer > ll = new LinkedList < Integer > ( Arrays . asList ( arr )); // rearrange the given list alternateSort ( ll ); } }C## Python program to rearrange a given list such that it # consists of alternating minimum maximum elements inp = [] # Function to rearrange a given list such that it # consists of alternating minimum maximum elements def alternateSort (): global inp # sort the list in ascending order inp . sort () # get index to first element of the list it = 0 it = it + 1 i = 1 while ( i < ( len ( inp ) + 1 ) / 2 ): i = i + 1 # pop last element (next greatest) val = inp [ - 1 ] inp . pop () # insert it after next minimum element inp . insert ( it val ) # increment the pointer for next pair it = it + 2 # Driver code # input list inp = [ 1 3 8 2 7 5 6 4 ] # rearrange the given list alternateSort () # print the modified list print ( inp ) # This code is contributed by Arnab KunduJavaScript// C# program to rearrange a given list such that it // consists of alternating minimum maximum elements using System ; using System.Collections.Generic ; class GFG { // Function to rearrange a given list such that it // consists of alternating minimum maximum elements // using List public static void alternateSort ( List < int > ll ) { ll . Sort (); for ( int i = 1 ; i < ( ll . Count + 1 ) / 2 ; i ++ ) { int x = ll [ ll . Count - 1 ]; ll . RemoveAt ( ll . Count - 1 ); ll . Insert ( 2 * i - 1 x ); } foreach ( int a in ll ) { Console . Write ( a + ' ' ); } } // Driver code public static void Main ( String [] args ) { // input list int [] arr = { 1 3 8 2 7 5 6 4 }; // convert array to List List < int > ll = new List < int > ( arr ); // rearrange the given list alternateSort ( ll ); } } /* This code contributed by PrinciRaj1992 */
Producción1 8 2 7 3 6 4 5Complejidad del tiempo: O(N*logN) ya que estamos usando una función de clasificación.
Espacio Auxiliar: O(1) ya que no estamos usando espacio adicional.
Enfoque n.° 2: usar sort()
Ordene la lista dada en orden ascendente Inicialice una lista de resultados vacía Itere sobre la mitad de los índices de la lista ordenada: Agregue el elemento del índice actual y el elemento correspondiente del final de la lista Si la longitud de la lista original es impar, agregue el elemento del medio a la lista de resultados Convierta la lista de resultados en una cadena con números enteros separados por espacios
Algoritmo
1. Ordene la lista usando la función sort()
C++
2. Inicialice una lista de resultados vacía
3. Recorra el rango de la primera mitad de la lista.
4. Agregue el i-ésimo elemento de la lista ordenada.
5. Agregue el (-i-1) -ésimo elemento de la lista ordenada
6. Si la longitud de la lista original es impar, agregue el elemento del medio a la lista de resultados.
7. Convierta la lista de resultados en una cadena usando la función join()Java#include#include #include using namespace std ; string alternateMinMax ( vector < int > lst ) { sort ( lst . begin () lst . end ()); vector < int > res ; for ( int i = 0 ; i < lst . size () / 2 ; i ++ ) { res . push_back ( lst [ i ]); res . push_back ( lst [ lst . size () - i - 1 ]); } if ( lst . size () % 2 == 1 ) { res . push_back ( lst [ lst . size () / 2 ]); } string result = '' ; for ( int i = 0 ; i < res . size (); i ++ ) { result += to_string ( res [ i ]) + ' ' ; } return result ; } int main () { vector < int > lst = { 1 3 8 2 7 5 6 4 }; cout < < alternateMinMax ( lst ) < < endl ; return 0 ; } Python3import java.util.ArrayList ; import java.util.Collections ; import java.util.List ; public class AlternateMinMax { // Function to rearrange a list of integers in alternating min-max order public static String alternateMinMax ( List < Integer > lst ) { // Sort the input list in ascending order Collections . sort ( lst ); List < Integer > res = new ArrayList <> (); // Iterate through the first half of the sorted list for ( int i = 0 ; i < lst . size () / 2 ; i ++ ) { res . add ( lst . get ( i )); res . add ( lst . get ( lst . size () - i - 1 )); } // If the input list has an odd number of elements add the middle element if ( lst . size () % 2 == 1 ) { res . add ( lst . get ( lst . size () / 2 )); } // Create a StringBuilder to build the result string StringBuilder result = new StringBuilder (); // Append each element from the rearranged list to the result string for ( int i = 0 ; i < res . size (); i ++ ) { result . append ( res . get ( i )). append ( ' ' ); } return result . toString (); } public static void main ( String [] args ) { // Create a list of integers List < Integer > lst = new ArrayList <> (); lst . add ( 1 ); lst . add ( 3 ); lst . add ( 8 ); lst . add ( 2 ); lst . add ( 7 ); lst . add ( 5 ); lst . add ( 6 ); lst . add ( 4 ); // Call the alternateMinMax function and print the result System . out . println ( alternateMinMax ( lst )); } }C#def alternate_min_max ( lst ): lst . sort () res = [] for i in range ( len ( lst ) // 2 ): res . append ( lst [ i ]) res . append ( lst [ - i - 1 ]) if len ( lst ) % 2 == 1 : res . append ( lst [ len ( lst ) // 2 ]) return ' ' . join ( map ( str res )) lst = [ 1 3 8 2 7 5 6 4 ] print ( alternate_min_max ( lst ))JavaScriptusing System ; using System.Collections.Generic ; using System.Linq ; public class GFG { public static string GetAlternateMinMax ( List < int > lst ) { // Sort the list in ascending order lst . Sort (); List < int > res = new List < int > (); int n = lst . Count ; // Create the alternating min-max list for ( int i = 0 ; i < n / 2 ; i ++ ) { res . Add ( lst [ i ]); res . Add ( lst [ n - i - 1 ]); } // If the list has an odd number of elements add the middle element if ( n % 2 == 1 ) { res . Add ( lst [ n / 2 ]); } // Convert the result list to a string string result = string . Join ( ' ' res ); return result ; } public static void Main ( string [] args ) { List < int > lst = new List < int > { 1 3 8 2 7 5 6 4 }; string result = GetAlternateMinMax ( lst ); Console . WriteLine ( result ); } }
Producción1 8 2 7 3 6 4 5Complejidad del tiempo: O (nlogn) debido a la operación de clasificación. El bucle for itera más de la mitad de la lista, lo que lleva O(n/2) tiempo. La conversión de la lista de resultados a una cadena lleva O(n) tiempo. Dado que O(nlogn) es mayor que O(n), la complejidad del tiempo general es O(n*logn).
Espacio auxiliar: O(n) porque la lista ordenada y la lista de resultados ocupan espacio O(n). El espacio utilizado por las variables utilizadas en la función es constante y no depende del tamaño de la lista de entrada.
