Rearanjați o listă dată astfel încât să fie compusă din elemente minime maxime alternative
#practiceLinkDiv { display: none !important; } Având în vedere o listă de numere întregi, rearanjați lista astfel încât să fie compusă din elemente minime maxime alternate folosind numai operațiuni de listă . Primul element al listei ar trebui să fie minim, iar al doilea element ar trebui să fie maxim dintre toate elementele prezente în listă. În mod similar, al treilea element va fi următorul element minim și al patrulea element este următorul element maxim și așa mai departe. Utilizarea spațiului suplimentar nu este permisă. Exemple:
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 Rearanjarea matricei Încearcă!Ideea este să sortați mai întâi lista în ordine crescătoare. Apoi începem să apară elemente de la sfârșitul listei și să le introducem în poziția lor corectă în listă. Mai jos este implementarea ideii de mai sus -
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 */
Ieșire1 8 2 7 3 6 4 5Complexitatea timpului: O(N*logN) deoarece folosim o funcție de sortare.
Spațiu auxiliar: O(1) deoarece nu folosim spațiu suplimentar.
Abordarea nr. 2: Folosind sort()
Sortați lista dată în ordine crescătoare Inițializați o listă de rezultate goală Iterați peste jumătate din indicile listei sortate: Adăugați elementul din indexul curent și elementul corespunzător de la sfârșitul listei Dacă lungimea listei originale este impară adăugați elementul din mijloc la lista de rezultate Convertiți lista de rezultate într-un șir cu numere întregi separate prin spațiu
Algoritm
1. Sortați lista folosind funcția sort().
C++
2. Inițializați o listă de rezultate goală
3. Parcurgeți în buclă intervalul din prima jumătate a listei
4. Adăugați elementul i al listei sortate
5. Adăugați elementul (-i-1)-al-lea din lista sortată
6. Dacă lungimea listei originale este impară, adăugați elementul din mijloc la lista de rezultate
7. Convertiți lista de rezultate într-un șir folosind funcția 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 ); } }
Ieșire1 8 2 7 3 6 4 5Complexitatea timpului: O(nlogn) din cauza operației de sortare. Bucla for repetă peste jumătate din listă, ceea ce durează O(n/2) timp. Conversia listei de rezultate într-un șir durează O(n) timp. Deoarece O(nlogn) este mai mare decât O(n), complexitatea generală a timpului este O(n*logn).
Spațiu auxiliar: O(n) deoarece lista sortată și lista de rezultate ocupă ambele spațiu O(n). Spațiul folosit de variabilele utilizate în funcție este constant și nu depinde de dimensiunea listei de intrare.
