Järjestä annettu luettelo uudelleen siten, että se koostuu vuorottelevista vähimmäismaksimielementeistä
Kokeile sitä GfG Practicessa 
#practiceLinkDiv { näyttö: ei mitään !tärkeää; }
#practiceLinkDiv { näyttö: ei mitään !tärkeää; } Kun on annettu kokonaislukuluettelo, järjestä lista uudelleen siten, että se koostuu vuorottelevista minimimaksimielementeistä käyttämällä vain luettelotoimintoja . Luettelon ensimmäisen elementin tulee olla minimi ja toisen elementin enimmäismäärä kaikista luettelossa olevista elementeistä. Samoin kolmas elementti on seuraava minimielementti ja neljäs elementti on seuraava maksimielementti ja niin edelleen. Ylimääräisen tilan käyttö ei ole sallittua. Esimerkkejä:
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 Järjestetään joukko uudelleen Kokeile sitä!Ajatuksena on lajitella luettelo ensin nousevaan järjestykseen. Sitten alamme ponnahtaa elementtejä luettelon lopusta ja lisäämme ne oikeaan paikkaan luettelossa. Alla yllä olevan idean toteutus -
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 */
Lähtö1 8 2 7 3 6 4 5Aika monimutkaisuus: O(N*logN), koska käytämme lajittelufunktiota.
Aputila: O(1), koska emme käytä ylimääräistä tilaa.
Lähestymistapa #2: Käytä sort()
Lajittele annettu lista nousevassa järjestyksessä Alusta tyhjä tuloslista Toista yli puolet järjestetyistä luetteloindekseistä: Liitä elementti nykyisestä indeksistä ja vastaava elementti luettelon lopusta Jos alkuperäisen luettelon pituus on pariton, lisää keskimmäinen elementti tulosluetteloon Muunna tuloslista merkkijonoksi, jossa on välilyönnillä erotettuja kokonaislukuja
Algoritmi
1. Lajittele lista käyttämällä sort()-funktiota
C++
2. Alusta tyhjä tulosluettelo
3. Selaa luettelon ensimmäisen puoliskon aluetta
4. Liitä lajitellun luettelon i. elementti
5. Liitä lajitellun luettelon (-i-1) -elementti
6. Jos alkuperäisen listan pituus on pariton, lisää keskimmäinen elementti tulosluetteloon
7. Muunna tuloslista merkkijonoksi käyttämällä join()-funktiotaJava#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 ); } }
Lähtö1 8 2 7 3 6 4 5Aika monimutkaisuus: O(nlogn) lajittelutoiminnon vuoksi. For-silmukka iteroi yli puolet listasta, mikä kestää O(n/2) aikaa. Tulosluettelon muuntaminen merkkijonoksi kestää O(n) aikaa. Koska O(nlogn) on suurempi kuin O(n), yleinen aikamonimutkaisuus on O(n*logn).
Apuväli: O(n), koska sekä lajiteltu lista että tuloslista vievät O(n) tilaa. Funktiossa käytettyjen muuttujien käyttämä tila on vakio, eikä se riipu syöttölistan koosta.
