#practiceLinkDiv { display: none! importante; }Data una lista di numeri interi riorganizzare la lista in modo che consista di elementi minimi massimi alternati utilizzando solo operazioni di elenco . Il primo elemento dell'elenco dovrebbe essere il minimo e il secondo elemento dovrebbe essere il massimo di tutti gli elementi presenti nell'elenco. Allo stesso modo il terzo elemento sarà l'elemento minimo successivo e il quarto elemento sarà l'elemento massimo successivo e così via. Non è consentito l'utilizzo di spazi aggiuntivi. Esempi:
Input: [1 3 8 2 7 5 6 4]Recommended Practice Riorganizzazione dell'array Provalo!
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]
L'idea è di ordinare prima l'elenco in ordine crescente. Quindi iniziamo a estrarre gli elementi dalla fine dell'elenco e a inserirli nella posizione corretta nell'elenco. Di seguito è riportata l'implementazione dell'idea di cui sopra:
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>
Produzione
1 8 2 7 3 6 4 5
Complessità temporale: O(N*logN) poiché stiamo utilizzando una funzione di ordinamento.
Spazio ausiliario: O(1) poiché non stiamo utilizzando spazio aggiuntivo.
Approccio n. 2: utilizzo di sort()
Ordina l'elenco fornito in ordine crescente Inizializza un elenco di risultati vuoto Itera oltre la metà degli indici dell'elenco ordinato: Aggiungi l'elemento dall'indice corrente e l'elemento corrispondente dalla fine dell'elenco Se la lunghezza dell'elenco originale è dispari aggiungi l'elemento centrale all'elenco dei risultati Converti l'elenco dei risultati in una stringa con numeri interi separati da spazi
Algoritmo
1. Ordina l'elenco utilizzando la funzione sort()
2. Inizializzare un elenco di risultati vuoto
3. Passare in rassegna l'intervallo della prima metà dell'elenco
4. Aggiungi l'i-esimo elemento dell'elenco ordinato
5. Aggiungi l'(-i-1)-esimo elemento dell'elenco ordinato
6. Se la lunghezza dell'elenco originale è dispari, aggiungi l'elemento centrale all'elenco dei risultati
7. Convertire l'elenco dei risultati in una stringa utilizzando la funzione 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));
Produzione
1 8 2 7 3 6 4 5
Complessità temporale: O(nlogn) a causa dell'operazione di ordinamento. Il ciclo for esegue l'iterazione su metà dell'elenco che richiede tempo O(n/2). La conversione dell'elenco dei risultati in una stringa richiede tempo O(n). Poiché O(nlogn) è maggiore di O(n), la complessità temporale complessiva è O(n*logn).
Spazio ausiliario: O(n) perché l'elenco ordinato e l'elenco dei risultati occupano entrambi lo spazio O(n). Lo spazio utilizzato dalle variabili utilizzate nella funzione è costante e non dipende dalla dimensione dell'elenco di input.