#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]Recommended Practice Reorganizar la matriz ¡Pruébalo!
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]
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++
// C++ program to rearrange a given list such that it // consists of alternating minimum maximum elements #include
// 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); } }
# 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 Kundu
// 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 */
<script> // JavaScript program to rearrange a given list such that it // consists of alternating minimum maximum elements let inp = [] // Function to rearrange a given list such that it // consists of alternating minimum maximum elements function alternateSort(){ // sort the list in ascending order inp.sort() // get index to first element of the list let it = 0 it = it + 1 let i = 1 while ( i < (inp.length + 1)/2 ){ i = i + 1 // pop last element (next greatest) let val = inp[inp.length-1] inp.pop() // insert it after next minimum element inp.splice(it0 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 for(let x of inp){ document.write(x' ') } // This code is contributed by shinjanpatra </script>
Producción
1 8 2 7 3 6 4 5
Complejidad 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()
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()
#include
import 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)); } }
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))
using 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); } }
function alternateMinMax(lst) { lst.sort((a b) => a - b); // Initialize an empty array to // store the result const res = []; for (let i = 0; i < Math.floor(lst.length / 2); i++) { // Push the minimum element from the beginning res.push(lst[i]); res.push(lst[lst.length - i - 1]); } // If the length of the list is odd // push the middle element if (lst.length % 2 === 1) { res.push(lst[Math.floor(lst.length / 2)]); } // Convert the result array to a // space-separated string const result = res.join(' '); return result; } // Input list const lst = [1 3 8 2 7 5 6 4]; console.log(alternateMinMax(lst));
Producción
1 8 2 7 3 6 4 5
Complejidad 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.